Question 10086 –

Consider the grammar

   S → bSe
   S → PQR
   P → bPc
   P → ε
   Q → cQd
   Q → ε
   R → dRe
   R → ε  

where S,P,Q,R are non-terminal symbols with S being the start symbol; b,c,d,e are terminal symbols and ‘ε’ is the empty string. This grammar generates strings of the form bⁱ, c^j, d^k, e^m for some i,j,k,m ≥ 0.
(a) What is the condition on the values of i,j,k,m?

(b) Find the smallest string that has two parse trees.

Correct Answer: A