Lemma 13.1: If G = (V, , S, P) is any context-free grammar, there is some stack machine M with L(M) = L(G).

Proof sketch: By construction. Let M be the stack machine M = (V U , , S, ), where the function is defined as follows:

for all v V, (, v) = {x | (v --> x) P}, and

for all a , (a, a) = {}. Now M accepts a string if and only if there is a derivation of that string in the grammar G. Thus L(M) = L(G).

Using the construction of Lemma 13.1, give a stack machine for this grammar: S --> XSY |

X --> a | b

Y --> c | d

Show accepting sequences of IDs for your stack machine for abcd and abbddd