retagged by
4,212 views
3 votes
3 votes
given Grammar

E → E + E

E → E * E

E → ( E )

E → id

Find set of handles and viable prefixes for the input string id1 + id2 * id3
retagged by

4 Answers

Best answer
12 votes
12 votes

viable prefix is -->

  • A string that equals a prefix of right-sentential form upto and even including its unique handle .
  • And also any prefix of a string that satisfies first.

E -> E + E -> E + E*E -> E + E * id -> E + id * id -> id + id * id

{Coloured is used to show Handle at each step}

Handle H = { E + E , E*E , Id }

Viable Prefix VP = { $\epsilon$ , E , E + , E + E , E + E * E , E + E *  , E + E * id , E + id , id  }

selected by
0 votes
0 votes

viable prefix is -->

  • A string that equals a prefix of right-sentential form upto and even including its unique handle .
  • And also any prefix of a string that satisfies first point.

E -> T -> F -> (E) -> (E+T) -> (E+T*F) -> (T+T*F) -> (F+T*F) -> (F+F*F) -> (id+F*F) -> (id+id*F) -> (id+id*id

(Bold part is a handle)

Now, by the definition of Viable Prefix 

for right sentential form (E+T*F) , where T*F is a handle, any prefix of this (E+T*F) is a viable prefix

i.e. E+T* is a viable prefix

Answer is a

0 votes
0 votes

$Handles=\{id,E+E,E*E\}$

$Viable\ prefixes=\{id,E,E+,E+id,E+E,E+E*,E+E*id,E+E*E\}$


$E$

$\underline{E+E}$

$E+\underline{E*E}$

$E+E*\underline{id}$

$E+\underline{id}*id$

$\underline{id}+id*id$


$E$

$\underline{E*E}$

$E*\underline{id}$

$\underline{E+E}*id$

$E+\underline{id}*id$

$\underline{id}+id*id$

0 votes
0 votes

First check the handles

$\left ( id+id*id \right ),id$

$\left ( F+id*id \right ),F$

$\left ( T+id*id \right ),T$

$\left ( E+id*id \right ),id$

$\left ( E+F*id \right ),F$

$\left ( E+T*id \right ),id$

$\left ( E+T*F \right ),T*F$

$\left ( E+T \right ),E+T$

$\left ( E \right ), \left ( E \right )$

$F,F$

$T,T$

$E$

So, handles are $\left (id,F,T,T*F,E+T,\left ( E \right ) \right )$


Now, check viable prefix

$.\left ( id+id*id \right )$

$\left (. id+id*id \right )$

$\left ( id.+id*id \right )$

$\left ( F.+id*id \right )$

$\left ( T.+id*id \right )$

$\left ( E.+id*id \right )$

$\left ( E+.id*id \right )$

$\left ( E+id.*id \right )$

$\left ( E+F.*id \right )$

$\left ( E+T.*id \right )$

$\left ( E+T*.id \right )$

$\left ( E+T*id. \right )$

$\left ( E+T*F. \right )$

$\left ( E+T. \right )$

$\left ( E. \right )$

$\left ( E \right ).$

$F.$

$T.$

$E$

Viable Prefix are $(, (id,(F,(T,(E,(E+,(E+id,$$(E+F,(E+T,(E+T*,(E+T*id,(E+T*F,(E+T,(E,(E),F,T,E$

Related questions