Lemma 13.2.1: If M=, , S, ) is any stack machine, there is context-free grammar G with L(G) L(M) Proof: By construction. We assume thatand have no elements in common. (This is without loss of generality since the symbols incan be renamed away from if necessary.) Let G be the grammar G-TT, S, P), where Now leftmost derivations in G exactly simulate executions of M, in the sense that for any x * and y E' S* xy if and only if (x, S) "(e,y) Lemma 13.2.1: If M=, , S, ) is any stack machine, there is context-free grammar G with L(G) L(M) Proof: By construction. We assume thatand have no elements in common. (This is without loss of generality since the symbols incan be renamed away from if necessary.) Let G be the grammar G-TT, S, P), where Now leftmost derivations in G exactly simulate executions of M, in the sense that for any x * and y E' S* xy if and only if (x, S) "(e,y)