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

**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 (q1, c, x, y, q2);

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

- 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.
- Our PDAs are
*non-deterministic*(given a configuration, multiple transitions may be possible, or none) - Example: PDA
*M*for {0_{1 }^{n}1^{m}: n >= 1, 1 <= m <= n} - Example: PDA
*M*for {0_{2 }^{n}1^{n}: n >= 0} (p. 115) *PDA design trick*: special "bottom of stack" character (**$**in our textbook)- PDA
*configuration*-- (state, remaining input, stack contents)

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

o
*ending* configuration (?,
empty input, any stack)

o
*accepting* configuration (final
state, empty input, any stack)

o
Every
transition takes one configuration to a different one.

- Stack contents is represented
as a string in Gamma*,
with the topmost character on the left
*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
- 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 is accepted by some 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*