Theory of Computation

Recitation 9, 05/15/01

- How many languages are there?
- Nondeterministic Pushdown Automata.
- Deterministic Pushdown Automata.
- Converting Context Free Grammars to Pushdown Automata.

- Could I ever write a computer program that enumerated (listed)
all the possible languages? What about one that enumerated all the
regular languages? What about one that enumerated all the
context-free languages?
## Pushdown Automata Warmup

- What is the difference between a Nondeterministic Pushdown Automaton and a Deterministic Pushdown Automaton. Do you think they generate the same languages?
- (Warm up) Construct a PDA that accepts the language {0,1}*.
- (Warm up from last time:) Construct a PDA that accepts the language
{0
^{n}1^{n}| n >= 0}. Is your answer deterministic or not? - Construct a PDA that accepts the language
{0
^{n}1^{n}| n >= 2}.## More Pushdown Automata

- Construct a PDA that accepts the language
{ 0
^{m}1^{n}| n > m >= 0} - (From last time:) Construct a PDA that accepts the language
{0
^{n}1^{m}0^{m}1^{n}| n,m >= 0}. - Construct a PDA that accepts the language { w | w is not a palindrome}
## And/Or

- Construct a PDA that accepts the language { w | w is not a palindrome and w ends with a zero}
- Give a PDA that accepts the language {a
^{i}b^{j}| i <= j <= 2i}## Deterministic vs Nondeterministic PDA's

- Construct a NPDA that accepts the language of strings with the same number of zeros and ones.
- Construct a DPDA that accepts the language of strings with
the same number of zeros and ones.
## Converting Grammars to PDA's

- Convert the following Grammar to a PDA.
S --> AB A --> 0 B --> 1

- Convert the following Grammar to a PDA.
A --> BAB | B | epsilon B --> 00 | espilon

Dimitri Kountourogiannis, dimitrik@alum.mit.edu