**Lecture
12 (Converting PDAs to CFGs), 10/9/17**

**Concepts, definitions (in italics):**

- Our PDAs are non-deterministic; shift-reduce parsers
are a
*deterministic*algorithm used in compilers, which is based on the PDAs we obtained from the CFG. They use*lookahead*(in the input) to decide which rule to use when*shifting*(i.e. replacing a variable on stack by its RHS). - Some languages have CFGs that need lookahead
1, others 2, etc;
- Known as LL(k) parsers, where k is the size of lookahead
- The 3 properties of
*simple*PDAs (p 121) - Single accept state
- Empty stack at end
- Each transition only pushes or pops a single character
*Simple*PDAs are as powerful as regular PDAs

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

- Why do we create these variations on grammars or
machines? They are useful!

·
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 V_{p,q}

o V_{p,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 V_{q}_{-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

- Theorem: For every CFG
*G*, there exists an equivalent PDA*M*. (did last time)_{G}

§ Because there is an algorithm that, given a CFG *G*, will
create an equivalent PDA M* _{G}*.

§ The proof that L(*G*) = L(*M _{G}*)
has two parts (if w is in L(G), it is accepted by M

- Theorem: For every PDA
*M*, there exists an equivalent CFG*G*(did today)_{M}

§ Because there is an algorithm that, given a simple PDA *M*, will create an equivalent CFG *G _{M}*.

§ The proof that L(*M*) = L(*G _{M}*)
has two parts (if w is accepted by M there is a derivation for it in

·
Closure rules for CFLs:

o Concatenation, union, star

·
CFLs
are *not* closed under intersection or complement

·
Proving that CFLs are not closed
under intersection:

- Let L
_{3}= {**a**^{n}**b**^{n}**c**^{*}: n ≥ 0} and L_{4}= {**a**^{*}**b**^{n}**c**^{n}: n ≥ 0}. - The intersection of L
_{3}and L_{4}is {**a**^{n}**b**^{n}**c**^{n}: n ≥ 0} - Both L
_{3}and L_{4}are context-free, but their intersection is not.

**Reading:**

- Chapter 2 through end of p. 125 (end of section 2.2)

**Skills:**

- Know new definitions, understand new concepts.
- Given a regular PDA, create an equivalent simple PDA.
- Given simple PDA, create equivalent CFG

·
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