Dual representations of PDA computation: as sequences of
transitions or of configurations
String-pushing PDAs
Converting a string-pushing PDA to a regular PDA
Being able to push strings does not add power to PDAs.
The 3 properties of simple PDAs
Converting a simple PDA to a regular one.
Simple PDAs are as powerful as regular PDAs
Converting a CFG to an equivalent string-pushing PDA.
Shift and reduce transitions.
Reading:
Chapter 2.2 through middle of p. 119
Skills:
Know new definitions, understand new concepts.
Given the description of a context-free language, find a PDA for it.
Given a PDA M and a string w, show an accepting computation
of M for w as a sequence of
configuration triples (current state, remaining input, stack contents).
Given two adjacent configurations in a PDA computation, what is the transition
that took place from one to the other?
Convert a string-pushing PDA to an equivalent regular PDA.
Convert a regular PDA to an equivalent simple PDA.
Given a CFG G, create an equivalent PDA.
Notes:
We saw PDA for {wwR: w over {a,b}}
Example of a language for which a non-empty stack is appropriate:
{anbm : n >= m}
When a string is pushed onto the stack, the leftmost character appears on
top.
The CFG for which we constructed a PDA is the one with equal numbers
of a's and b's