Viable Prefix

Question

Linked Answer Questions: Q. 80 to Q. 81 .
Consider the following grammar production
\[
\begin{array}{l}
\mathrm{S} \rightarrow \mathrm{BB} \\
\mathrm{~B} \rightarrow \mathrm{aB} \mid \mathrm{b}
\end{array}
\]
Q. 80 LR(1) item [ $B \rightarrow a \cdot B, a]$ is a valid for which of the following viable prefix?
(a) a
(b) aa
(c) aaa
(d) Baa
Q. 81 LR(1) item $[B \rightarrow a \cdot B, S]$ is a valid for which of the following viable prefix?
(a) a
(b) Baa
(c) $a a B$
(d) Bab

Linked Answer Questions: Q. 82 to Q.83.
(b) Even Positive Inte
(c) Even and Odd bs
(d) None of these

Linked Answer Questi
Consider a system segmentation. The virtus of up to 8 segments an bytes long. The hardw into $2^{8}$ byte pages.
Q. 84 How many bits the segment nu
(a) 1 bit
(c) 3 bits

Consider the algorithm below

Comments

For 80 , I m getting (A),(B),(C),(D) all. And for 81, I m getting (B). Can anyone verify this?

Answer 1

80 . LR(1) item B---> a.B,a  is valid for " aaa ". 

 A---> a'.ß, a'' is valid for viable prefix let y if there is derivation S-rm*-->ØAw---> Øa'ßa''w

here y=Øa' here a'' is lookahead , which is first symbol of w so for given question 

S--> BB---> BaB--->--> Bab---> aBab-*-->aaaBab(rightmost derivation)  so here a''=a , w=ab ,Ø=aa,

viable prefix = aaa 

81. similar here S--> BB --> BaB--> BaaB 

so w=∊ ,a''=$  ,a'=a , Ø=Ba so

y=  Baa..

reference http://www.cs.clemson.edu/course/cpsc827/material/LRk/LR1.pdf

http://tinman.cs.gsu.edu/~raj/4340/sp12/LR1.pdf

Comments

For the first part, can't it be

S -> BB, S-> BaB,S-> Bab, S -> aBab

This way, a is th prefix.

---

@Sonam , what is viable prefix ? Can you explain it with a simple example ??

Answer 2

Viable prefix : The prefixes of right sentential forms that can appear on the stack of a shift-reduce parser are called viable prefixes.

Simple design LR(1) DFA. then u get the ans. Ans will be d and b respectively.

follow this : http://www.cs.cornell.edu/courses/cs412/2007sp/lectures/lec09.pdf

Comments

Okay! :(

---

The answer should be -

(54) - d

(55) - a

---

Hello , for the first one if we draw the dfa and go through the dfa states by using the string aaa or aaaa then also we reach a state which is similar to the state which is reached if we use the string a.And that state also contain the mentioned item then why the answer is d only ??

Please clarify.

Answer 3

answer  is option ( c ) aaa

so in B-->a.B,a            a    after ,   is   lookahead   

by   deriving stings  we  have to check rightmost derivation

since vaid  viable prefix for item B-->a.B,a   will   be  'y'  in  S==> yBx   such that there is a  RMD  in which  x  should have starting symbol as   ' a ' (  corresponds to lookahead symbol)

so  according to given derivation-->

S==>BB==>aBB==>aBaB==>aaBaB==>aaaBaB==>aaaBab      here   y=aaa  ,    B=B   ,   x=ab   and  starting symbol of x is ' a ' .

which is given in option is also   ( c ) aaa.

hence answer  is option ( c ) aaa

Comments

why aa is not viable prefix here.. here we have read a and hope to read another a 

src : http://www.cs.williams.edu/~tom/courses/434/outlines/lect14_2.html

 viable prefix is that something is a viable prefix of a sentential form it it extends up to but not past the handle..

as per the above definition aa can also be a viable prefix.

Please point where i m getting this wrong

---

S==>BB==>BaB==>Bab==>aBab     here   y=a, why is this wrong ?? .