**Lecture
11 (Converting CFGs to PDAs), 10/4/17**

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

- PDA
*configuration*– a triple (state, stack contents, remaining input) *Starting*configuration = (start state, complete input string remaining, empty stack)*Ending*configuration = (final state, empty remaning, any stack)- Implementing a PDA with a counter for L1 = {w : w in {a,b}* where #a’s = #b’s}
- Why can’t just put actual numbers on the stack?
- PDAs that
*push strings* - When a string is pushed onto the stack, the leftmost
character appears on top.
- Converting a PDA that pushes strings to one that pushes
single symbols onto the stack. (p.
119)
- Being able to push strings (rather than individual
symbols) does not add power to PDAs, though it adds convenience
- A regular PDA is a special case of a string-pushing
PDA which happens to never push strings longer than 1 character
- Can simplify the PDA for L1 by using strings
- Constructing a
*string-pushing*PDA from a CFG. - 2 types of transitions: shift, reduce
- Diagram looks similar to the PDA for L1
- Example:
**abbaaa** - Show CFG, number all rules
- Show tree for
**abbaaa**and corresponding leftmost derivation, with rules numbered - Convert CFG to string-pushing PDA
- Show PDA computation, how it
*corresponds*to the left-most derivation of CFG

**Reading:**

- Chapter 2.2 through middle of p. 121 (up to Lemma 2.27)

**Skills:**

- Know new definitions, understand new concepts.
- Given a string-pushing PDA, create an equivalent
regular PDA.
- Given a CFG G, create an equivalent string-pushing PDA.
- Given a leftmost derivation in CFG G, find the
corresponding computation in the string-pushing PDA, and vice versa.

**Notes:**

- The grammar for which we constructed a PDA is the one
for simple expressions:

o X -> XX | epsilon | aXa | bXb