Question 49

**hunterhogan** · 09-30-2003, 12:57 PM

I have never seen a DFA that uses notation _in_ the states like this question does. I am having a hard time understanding how to find the correct answer. Does anyone know of a book or website where I can see questions like this?

thanks

**wood** · 09-30-2003, 10:16 PM

It is indeed a bit strange.

When I faced that problem, I solved it through elimination to be frank.

I know that the final/accepting states have to be the bottom ones, since they are the only ones who end with a DOT.

So, (A) would end on the upper right state (big one), which has no production with a DOT at the end; (B) would be the same thing; (C) cannot be the one, 'cause there's no production from the bottom left state that accepts another b; and (E) is unlikely cause the start state is not a final/accepting state.

So the answer is (D).

I'm sure somebody can explain it better than me.

Wood

**hunterhogan** · 10-01-2003, 07:06 PM

i think that this is about as good an explanation as there is.

thanks!

**Laks** · 10-08-2003, 11:08 AM

Wood,
great work!!!

Hey this parsing automaton is very similar to LR parsing automaton that appears in Aho,Ullman Sethi (Compilers)

Keep going great guns....

Cheers'
Laks

**The_Wonderful_Vipul** · 10-08-2003, 01:40 PM

right Laks ( parser for LR grammar),

just did it today in class .... lemme put it in a better way

the place where the dot is indicates the point you r at .

e.g. while parsing abcd, a.bcd means that you have seen an a and now r expecting a b in the input. similarly ab.cd means that you have seen ab n are expecting c to parse the string correctly.

Thus, when you see abcd. , means you have seen the string completely and hence, the expression is parsed correctly i.e. you have reached a final state.

therefore, X1X2X3X4.... Xn take it from A-> .& to A->&. if A=>..... &.

hth
Vipul.

**eyeash** · 10-29-2003, 03:54 PM

So wood is it always a true statement that if something ends with a dot it is the end statement. Because if that is true then you are right this is an easy one too just disqualify answers and yes D would be the only one that goes to a dot.

Thanks

**nonevent99** · 10-29-2003, 04:43 PM

Maybe you guys want to try this one out:

http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8363

**telars** · 12-04-2003, 03:52 PM

The book "Introduction to Automata Theory, Langauages and Computation" by Hopcroft and Ulman talks about this to some extent in chapter 10. Look for the subsection on LR(0) grammars.

Tait