648 views
Consider the following grammaer:
S->0S1 | 01

How many of the following  are the viable prefixes of the grammar?
i.  01
ii. 001
iii. 00011
iv. 00S1

PS: given answer i, ii and iv , please explain!
edited | 648 views

Check the link for explaination :- https://gateoverflow.in/68764/bottom-up-parsing

$S\rightarrow 01$

$S\rightarrow 0S1\rightarrow 0011$

$S\rightarrow 0S1\rightarrow 00S11$

Set of Viable Prefix $V = \left \{ \epsilon ,0,1,01,0S,0S1,00,001,00S,00S1 \right \}$

answered by Veteran (50.6k points)
selected by
+1
0
@kapil why iii) is not viable?
0
Latex was not working :)
0
@Anusha, its not !! Instead $0001$ or $000S1$ is VP.
+1
sorry got it! 00011 never appears on top of the stack isnt it @kapil?
upto 0001 appears on top then 01 reduces S..so 00S will be stack content
but 00011 will never be stack content
+1
yes got it
0

I am not getting one thing..According to the link u given..can't we write like this:

S->0S1-->00S11-->000111{Bold one's are handle}

{VIABLE PREFIX--> epsilon,0,0S,0S1,00,00S,00S1,00S11,000,0001,00011,000111}

What is wrong in this??

0

@Lucky.

See here

0
please expain how you taken  1,0S as a viable prefix
0

@Kapil sir i dont think 1 would be viable prefix

....
answered by Boss (12.4k points)
edited

1