Consider the grammar where S, P, Q, R are non-terminal symbols with S being the start symbol; b, c, d, e are terminal symbols and epsilon is the empty string. S -> bSe | P P -> bPe | Q Q -> cQd | R R -> e This grammar generates strings of the form b^i 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.

GATE 1997 · Compiler Design · Grammar · medium

Answer: a. Condition: i = m and j = k (with i, j >= 0), so the language is {b^i c^j e d^j e^i | i,j >= 0}. b. The smallest string with two parse trees is 'bee' (length 3): derivable as S->bSe->...->bee and S->P->bPe->...->bee.

1. Trace a general derivation: Let S -> bSe be applied n_S times, then S -> P: gives b^(n_S) P e^(n_S). Let P -> bPe be applied n_P times, then P -> Q: gives b^(n_S+n_P) Q e^(n_S+n_P). Let Q -> cQd be applied n_Q times, then Q -> R: gives b^(n_S+n_P) c^(n_Q) R d^(n_Q) e^(n_S+n_P). Now R -> e: gives b^(n_S+n_P) c^(n_Q) e d^(n_Q) e^(n_S+n_P). So the string is b^(n_S+n_P) c^(n_Q) e d^(n_Q) e^(n_S+n_P). Let a = n_S + n_P (total b-count), q = n_Q. String: b^a c^q e d^q e^a.
2. Identify the string pattern and condition: The string has the form b^i c^j e d^k e^m where comparing: i = a, j = q, k = q, m = a. So j = k and i = m. These are the conditions. In the notation of the question (b^i c^j d^k e^m — but note there is an extra 'e' from R stuck between c's and d's, so the shape is really b^i c^j [e] d^j e^i). Condition: j = k and i = m, with i >= 0, j >= 0.
3. Find ambiguity: smallest string with two parse trees: Consider the string 'bce' (a=1, q=0): b^1 c^0 e d^0 e^1 = b e e. That's 'bee', not 'bce'. For q=1, a=0: c e d = 'ced'. For a=1, q=1: b c e d e = 'bcede'. Now can 'bcede' have two parse trees? Derivation 1: S -> bSe -> bPe -> bQe -> b(cQd)e -> b(cRd)e -> bcede (R->e gives 'e' between c and d, then outer e at end: b c e d e). Length 5. Derivation 2: Is there another way? S->P->bPe->bQe->bcQde->bcRde->bc(e)de... that gives bcede too but via P path first: S->P->bPe->bQe->b(cRd)e->b(c e d)e = bcede. Same string different derivation (S->P->bPe vs S->bSe->bPe — these ARE different derivations of the same string 'bcede'). Derivation 1 uses S->bSe first, Derivation 2 uses S->P->bPe first. Both give the string 'bcede', so 'bcede' (length 5) has two parse trees. Smaller candidates: 'bee' (a=1,q=0): S->bSe->bPe->bQe->bRe->bee. S->bSe->bPe->bQe->bee (Q->R->e). Any other derivation of 'bee'? S->P->bPe->bQe->bRe->bee. Yes! So 'bee' (length 3) also has two derivations.