In class, we proved that every language recognized by some pushdown automaton has a context-free grammar that generates it (Lemma 2.27 in the book). (a) At the beginning of the proof, there were three modifications that we made to the automaton before using it to create the grammar. Take the following pushdown automaton and follow the method from the proof to find an equivalent automaton fitting all three requirements. (b) The following pushdown automaton already meets the requirements needed for the proof. Follow the method from the proof to create a context-free grammar that generates the language that this automaton recognizes. You should include all the rules and variables that the method describes, even those that can never be used to generate a complete string. LEMMA 2.27 If a pushdown automaton recognizes some language, then it is context free. PROOF IDEA We have a PDA P, and we want to make a CFG G that generates all the strings that P accepts. In other words, G should generate a string if that string causes the PDA to go from its start state to an accept state. To achieve this outcome we design a grammar that does somewhat more. For each pair of states p and q in P the grammar will have a variable Apq. This variable generates all the strings that can take P from p with an empty stack to q with an empty stack. Observe that such strings can also take P from p to q, regardless of the stack contents at p, leaving the stack at q in the same condition as it was at p. First, we simplify our task by modifying P slightly to give it the following three features. 1. It has a single accept state, qaccept. 2. It empties its stack before accepting. 3. Each transition either pushes a symbol onto the stack (a push move) or pops one off the stack (a pop move), but it does not do both at the same time. Giving P features 1 and 2 is easy. To give it feature 3 , we replace each transition that simultaneously pops and pushes with a two transition sequence that goes through a new state, and we replace each transition that neither pops nor pushes with a two transition sequence that pushes then pops an arbitrary stack symbol. To design G so that Apq generates all strings that take P from p to q, starting and ending with an empty stack, we must understand how P operates on these strings. For any such string x,P 's first move on x must be a push, because every move is either a push or a pop and P can't pop an empty stack. Similarly, the last move on x must be a pop, because the stack ends up empty. Two possibilities occur during P 's computation on x. Either the symbol popped at the end is the symbol that was pushed at the beginning, or not. If so, the stack is empty only at the beginning and end of P 's computation on x. If not, the initially pushed symbol must get popped at some point before the end of x and thus the stack becomes empty at this point. We simulate the former possibility with the rule ApqaArsb, where a is the input read at the first move, b is the input read at the last move, r is the state following p, and s is the state preceding q. We simulate the latter possibility with the rule ApqAprArq, where r is the state when the stack becomes empty. 120 CHAPTER 2/ CONTEXT-FREE LANGUAGES PROOF Say that P=(Q,,,,q0,{qaccept}) and construct G. The variables of G are {Apqp,qQ}. The start variable is Aq0,qoccept. Now we describe G 's rules. - For each p,q,r,sQ,t, and a,b, if (p,a,) contains (r,t) and (s,b,t) contains (q,), put the rule ApqaArsb in G. - For each p,q,rQ, put the rule ApqAprArq in G. - Finally, for each pQ, put the rule App in G. You may gain some insight for this construction from the following figures. FIGURE 2.28 PDA computation corresponding to the rule ApqAprArq FIGURE 2.28 PDA computation corresponding to the rule ApqAprArq FIGURE 2.29 PDA computation corresponding to the rule ApqaArsb 2.2 PUSHDOWN AUTOMATA 121 Now we prove that this construction works by demonstrating that Apq generates x if and only if (iff) x can bring P from p with empty stack to q with empty stack. We consider each direction of the iff as a separate claim
