Solved

# NFSA language

Posted on 2008-10-29
211 Views
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

fa211.bmp
0
Question by:perdoname_
• 5
• 5
• 2

LVL 22

Accepted Solution

blu earned 300 total points
ID: 22831524
I think that aabb is also accepted:

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

LVL 22

Expert Comment

ID: 22832305
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

LVL 22

Expert Comment

ID: 22832373
I presume that e is short for the empty string.
0

LVL 27

Expert Comment

ID: 22840503
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

LVL 22

Expert Comment

ID: 22841759
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

LVL 22

Expert Comment

ID: 22841770
Twenty years? Try thirty. I bought my copy in 1979.
0

LVL 27

Expert Comment

ID: 22841975
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

LVL 22

Expert Comment

ID: 22842162
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

LVL 22

Assisted Solution

ID: 22842322
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

LVL 27

Expert Comment

ID: 22842337
>>I didn't see any other questions from you.

Not from me, from the questioner!
0

LVL 27

Expert Comment

ID: 23211472
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

LVL 27

Expert Comment

ID: 23213040
Split: blu (ID: 22831524) 60% Nova (ID: 22842322) 40%
0

## Featured Post

A short article about a problem I had getting the GPS LocationListener working.
Displaying an arrayList in a listView using the default adapter is rarely the best solution. To get full control of your display data, and to be able to refresh it after editing, requires the use of a custom adapter.
Viewers will learn how to properly install Eclipse with the necessary JDK, and will take a look at an introductory Java program. Download Eclipse installation zip file: Extract files from zip file: Download and install JDK 8: Open Eclipse and …
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…