**Lecture
10 (Push-down Automata), 10/2/17**

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

*Pushdown Automata*(PDAs): NFAs with a*stack –*we*push*symbols onto the stack and*pop*from the stack, one at a time- Formal definition (p. 113): PDA
= (Q, Sigma, Gamma, delta, q
_{0}, F) - PDA
*transitions*in delta: 5-tuples of the form (q, c, x, x’, q’);

- Start in state q, read char c,
pop stack x, push stack x’, go to state q’
- the label on the arrow would
be c,x -> x’

- To start computation, a PDA
must be in initial state and have empty stack
- Can only make transition that
reads
**c**(in Sigma) and pops**a**(in Gamma) if the remaining input starts with**c**and the stack has**a**on top - To accept a string, a PDA must
be in a final state and have read all the input (just as for FSAs);
however, it need not have an empty stack.
- Example: PDA
*M*for {0_{1 }^{n}1^{n}: n >= 1, 1 <= m <= n} - Example: PDA
*M*for {0_{1 }^{n}1^{n}: n >= 0} (p. 115) *PDA design trick*: special “bottom of stack” character ($ in our textbook)- PDA
*configuration*– (state, stack contents)

o
*Starting* configuration (initial
state, empty stack)

o
*ending* configuration (final
state, any stack)

o
Every
transition takes one configuration to a different one.

*A valid accepting*PDA computation is a sequence of PDA transitions- It starts in a starting configuration, reads the whole
input string, and ends in an ending configuration
- Example: PDA
*M*for {_{2 }*ww*: w over {^{R}**a**,**b**}* } (p. 116) - Our PDAs are
*non-deterministic*(given a configuration, multiple transitions may be possible, or none). - Deterministic PDAs can also be
defined; their
*expressiveness*is not the same, but between that of DFAs/NFAs and of PDAs

- 0
^{n}1^{n }can be done with deterministic PDA *ww*^{R}can’t^{ }

- PDA, PDA computation, language
of a PDA:
*formal definitions* - NFAs are a
*special case*of PDAs (which*ignores*its stack) - PDAs are strictly more powerful
(i.e. have
*greater expressiveness*) than NFAs (we saw one for {0^{n}1^{n}}) - We will be showing that CFGs
and PDAs have the same expressiveness.
- This will give us an alternate
definition of a CFL: one that can be generated with a PDA.
- Example: PDA
*M*for {_{3 }*w*over {**a**,**b**}* :*w*contains equal number of**a**'s and**b**'s} - This is a context-free
language, because there is a CFG for it
- It is not regular, because of
its intersection with a*b*
*PDA design trick*: using stack as a counter

**Reading****:**

- Chapter 2.2 to end of p. 116

**Skills:**

·
Know new definitions,
understand new concepts.

·
Given a PDA *M* and
a string *w*, show an accepting computation of *M* for *w* as
a sequence of configurations and transitions

·
Understand why NFAs
are a special case of PDAs

**Notes:**

Question: design a PDA for the language *L* =
{*w* in {**a**,**b**}*
: *w* contains equal number of **a**'s and **b**'s}.

1. Consider any string *w* in *L*.
Imagine going along the string from left to right keeping a tally as follows:
Start the tally at 0, add 1 for every **a**, subtract 1 for every **b**.
Our tally will be 0 at the end, and it may also be 0 in places along the way.
Here is an example for **aabbba**, where we show
the characters and the tally

_{0} ^{a}_{1} ^{a}_{2} ^{b
}_{1} ^{b}_{0} ^{b}_{-1}** ^{a}**

2. Use the stack to keep tally, with n **1**’s to represent positive number *n* and n **-1**s to represent negative number -*n*