Compiler: Viable Prefixes

Question

Consider the following grammar:
$S\rightarrow0S1 | 01$

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

PS: given answers i, ii and iv , please explain!

Answer 1

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 \}$

Comments

not readable!

---

@kapil why iii) is not viable?

---

Latex was not working :)

---

@Anusha, its not !! Instead $0001$ or $000S1$ is VP.

---

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

---

yes got it

---

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??

---

@Lucky.

See here

---

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

---

@Kapil sir i dont think 1 would be viable prefix