Lecture 12 (Converting PDAs to CFGs), 10/9/17
Concepts, definitions (in italics):
o Converting a regular PDA to a simple PDA
o Involves three steps, that must be done in order (to avoid undoing a condition)
o Note that if we start and end with empty stack, first transition always pushes and last one always pops
· For every simple PDA, there is an equivalent CFG
· Proof involves an algorithm for converting a simple PDA to a CFG
o All non-terminals are of the form Vp,q
o Vp,q corresponds to the set of strings that can be accepted as we go from state p to q, starting and ending with empty stack
o Vq-inital,q-final is the start variable
o Three types of rules created
· The set of languages accepted by PDAs is the same as generated by CFGs
§ Because there is an algorithm that, given a CFG G, will create an equivalent PDA MG.
§ The proof that L(G) = L(MG) has two parts (if w is in L(G), it is accepted by MG, and vice versa) both done by induction.
§ Because there is an algorithm that, given a simple PDA M, will create an equivalent CFG GM.
§ The proof that L(M) = L(GM) has two parts (if w is accepted by M there is a derivation for it in GM, and vice versa), both done by induction.
· Closure rules for CFLs:
o Concatenation, union, star
· CFLs are not closed under intersection or complement
· Proving that CFLs are not closed under intersection:
· Understand the role that recursion plays in proving that for every valid computation of simple PDA, there is an equivalent valid parse tree of the CFG