NFSA language

Hey,
I've got the following nondeterministic finite automaton which i want to check whether it accepts three words
abb, abbb, aabb

That's what i thought :
=================

abb = accepted

q0 , e  
q1 , a
q2 , b
q3 , b  {abb}
q4 ,   [since q4 is the final state the word is accepted ]

abbb = not accepted
aabb = not accepted
 
can someone check my answer ?
Please let me know if im doing something wrong  

Thanks in advance1

fa211.bmp
perdoname_Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Brian UtterbackPrinciple Software EngineerCommented:
I think that aabb is also accepted:

q0, a -> q6
q6, a -> q5
q5, b -> q5
q5, b -> q5
q5, e -> q4
Accepted.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
NovaDenizenCommented:
There's something going on that confuses me.  You say that this NFA accepts "abb" but then you show a path that "eabb" takes through it to demonstrate this fact.  Why are you adding the 'e' in at the beginning?

That being said, I can see that "eabb", "eabbb", and "aabb" are all accepted in this NFA.
0
Brian UtterbackPrinciple Software EngineerCommented:
I presume that e is short for the empty string.
0
Ultimate Tool Kit for Technology Solution Provider

Broken down into practical pointers and step-by-step instructions, the IT Service Excellence Tool Kit delivers expert advice for technology solution providers. Get your free copy now.

BigRatCommented:
Well the diagram is wrong in q6. This state transfers to itself on "a" and also it transfers to state q7 on "a".

Blu: there is no way to transfer from one state to another on an "empty" token. Either the input string has come to an end or it has not. You could theoretically have a state to which one would "go" when the input exhausts, but that state MUST be a final state and cannot transfer to any other state (which he has in his diagram)

BTW, I remember putting in some effort on similar questions two weeks ago. After returning from a business trip, I found no mention of them in E-E. Can somebody tell me what happened.

PS: I really think our questioner should get out the "Dragon Book" on compiler construction from his local library. There's an excellent tutorial on all of these techniques in it. What's the title of the book? I'll leave you to guess, but it has a dragon on the front and is a good twenty years old!
0
Brian UtterbackPrinciple Software EngineerCommented:
You are wrong BigRat. Look again at the original question. The author specifically specified a "nondeterministic" FSA.  The features that distinguish a nondeterministic one from a deterministic one is allowing the empty string as input and to have more than one transition from a state based on the same input. In a NFSA, the string is accepted if there is any transition path through the machine that ends in an accept state. With an NFSA there may be many paths through the machine given the same input string.
0
Brian UtterbackPrinciple Software EngineerCommented:
Twenty years? Try thirty. I bought my copy in 1979.
0
BigRatCommented:
Blu: "an empty string as input" is not the same as "an empty word followed by words". The transition from q0 to q1 may be allowed on an "empty input string", but subsequent transitions are not possible, for then the input would not have been empty. What is meant by "e" in that context is "not 'a' in the vocabulary", which is then "b".

I'll accept your point regarding q5 and q6, which would normally be merged.

But what about the previous questions? Were they deleted? I got no notifs.
0
Brian UtterbackPrinciple Software EngineerCommented:
No, NFSA-epsilon allows the empty symbol as a transition token. You are thus allowed to move from one state to another without consuming any characters from the input string. Such transitions are designated epsilon transitions and are denoted by an epsilon on the transition line. I presume that the author used "e" in place of epsilon here.  I admit it took me a while to realize this was done, and I thought of both interpretations you gave before realizing what was probably intended.

I didn't see any other questions from you. Better check the comments.
0
NovaDenizenCommented:
Ok, if e is epsilon, it makes more sense.

Here's how you verify abbb.

At start, the state is just the singleton { q0 }.  
There is an epsilon from q0, so the possible states become {q0, q1}.  
There aren't any more epsilons from q1.
now add 'a'. From q0 we can reach q6.  From q1 we can reach q2.  So after 'a', our possible states are { q2, q6 }.
There are no epsilons from q2 or q6, so we stay at {q2, q6}.
Add the first 'b'.  From q2, we can go to q1 or q3.  We can't get anywhere from q6.  So our possible states are { q1, q3 }.
No epsilons are available from q1 or q3.
Add the second 'b'.  From q1, we can go to q3.  From q3 we can go to q4.  So our states are {q3, q4}.
No epsilons.
Add the third 'b'.  From q3 we can get to q4.  From q4 there are no paths for 'b'.  So our state is just the singleton set { q4 }.
That's the end of the string.  Are any of our states an accept state?  We just have q4, and it is an accept state, so 'abbb' matches the NFSA.
0
BigRatCommented:
>>I didn't see any other questions from you.

Not from me, from the questioner!
0
BigRatCommented:
perdoname has posted a number of questions about autonoma which have been deleted after several people have attempted to answer the question. Again it seems that a question is to be deleted after blu (mostly) NovaDenizen and I have replied. I think blu should get most points.
0
BigRatCommented:
Split: blu (ID: 22831524) 60% Nova (ID: 22842322) 40%
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.