retagged by
702 views
2 votes
2 votes
S - >aSb | c

Give viable prefix for this with details of how to find viable prefix? for string - - aacbb
retagged by

1 Answer

Best answer
5 votes
5 votes

First of all we have to know a few points regarding viable prefix :

a) Viable prefixes w.r.t a string to be parsed are those which  appear in the stack during the process of reduction.

b) And secondly this should be a prefix of some right sentential form

STACK                     INPUT                      ACTION  

   $                          aacbb                          Shift

   $a                        acbb                            Shift

   $aa                      cbb                              Shift

   $aac                    bb                                Reduce

   $aaS                    bb                                Shift

   $aaSb                  b                                  Reduce

   $aS                     b                                  Shift

   $aSb                   $                                  Reduce

   $S                      $                                   Accept

Now we write the right sentential forms of the string "aacbb"

S  -->   aSb  --> aaSbb  -->  aacbb

One can verify that all of the given stack contents are prefix of one of the given 4 right sentential forms of the given string.

Hence the viable prefixes are : 

a , aa , aac , aaS , aaSb , aS , aSb , S 

selected by

Related questions

0 votes
0 votes
0 answers
1
Prince Sindhiya asked Jul 24, 2018
401 views
$\text{Generate the 3 address code for}$i=1; while(i<10) { x=0; i=i+1; }And find the least no. Of temporary variable required to create a 3 address code in static single ...