The correspondence between left-most derivations of a CFG and computations
of the corresponding PDAs.
Theorem: For every CFG, there exists an equivalent PDA.
Shift-reduce parsers
Shift-reduce parsers use lookahead (in the input) to decide which
rule to use in shifting.
Converting a simple PDA to a CFG
Theorem: For every PDA, there exists an equivalent CFG.
The set of languages accepted by PDAs is the same as generated by CFGs;
these are the CFLs
Reading:
Chapter 2 to end of section 2.2
Skills:
Know new definitions, understand new concepts.
Given a leftmost derivation in CFG G, find the corresponding computation
in the PDA MG, and vice versa.
When converting a simple PDA M to a CFG GM,
understand how the variables of GM relate to the states of
M: what is the correspondence
between strings generated by variables of GM and
computations of M? What is the start variable and why?
Notes:
The CFG for which we constructed a PDA is the one with equal numbers
of a's and b's; the string we used is aabbba
The PDA for which we might want to construc a CFG is the one for {0^n 1^n : n >= 1}
The proof that L(M) = L(GM) has two parts (claims
2.16 and 2.17 in the book), both done by induction.
The proof that L(G) = L(MG) has two parts,
both done by induction.