TestMagic

hunterhogan · 09-30-2003, 01: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, 11: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, 08:06 PM

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

thanks!

Laks · 10-08-2003, 12:08 PM

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, 02: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, 04: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, 05: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, 04: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

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

09-30-2003, 01:57 PM	#1 (permalink)
hunterhogan Trying to make mom and pop proud Join Date: Sep 2003 Posts: 15	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

09-30-2003, 11:16 PM	#2 (permalink)
wood TestMagic Guru Join Date: Jul 2003 Location: Brazil Posts: 1,360	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

10-01-2003, 08:06 PM	#3 (permalink)
hunterhogan Trying to make mom and pop proud Join Date: Sep 2003 Posts: 15	i think that this is about as good an explanation as there is. thanks!

10-08-2003, 12:08 PM	#4 (permalink)
Laks Eager! Join Date: Oct 2003 Location: India Posts: 35	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

10-08-2003, 02:40 PM	#5 (permalink)
The_Wonderful_Vipul Here I am !! Join Date: Feb 2003 Location: New York Posts: 165	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.

10-29-2003, 04:54 PM	#6 (permalink)
eyeash Trying to make mom and pop proud Join Date: Oct 2003 Posts: 19	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

10-29-2003, 05:43 PM	#7 (permalink)
nonevent99 TestMagic Guru-in-Training Join Date: Oct 2003 Location: USA Posts: 508	Maybe you guys want to try this one out: http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8363

12-04-2003, 04:52 PM	#8 (permalink)
telars Trying to make mom and pop proud Join Date: Oct 2003 Location: USA Posts: 17	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

TestMagic

Free GMAT, GRE, SAT Test, TOEFL practice tests