Topics
In our previous lecture, we introduced the class of context-free
languages as the class of languages that are generated by context-free
grammars. In this lecture, we shall see that, as the regular languages
are precisely those that are recognized by finite state automata, the
context-free languages are those that are recognized by pushdown
automata (PDA). PDA are essentially finite automata that can use
an unbounded stack as auxiliary memory.
PDA were first introduced by Oettinger in 1961. Afterwards, Chomsky,
Evey and Schutzenberger showed that context-free grammars and PDA are
equally expressive. This equivalence proof, like the one we presented
between regular expressions and finite automata, is
algorithmic.
Unlike for finite automata, the nondeterministic version of PDA is
strictly more powerful than the deterministic PDA. One can show that
there are context-free languages that can only be recognized by
nondeterministic PDA. These proofs are beyond the scope of this
introductory course.
Time and Location
Wednesday, 1 December 2004 at 9:00 in room 303.
Reading Material
Exercises
- (*) A right-linear grammar is a CFG whose productions
have either the form A --> wB or the form A --> w, where A and B are
variables and w is a string of terminals. What class of languages do
these grammars generate? What is the simplest subclass of pushdown
automata that recognize these languages? Argue for your answers.
- Exercises 2.5(e)(*), 2.7(c)(*) and 2.11 on pages 120-121 of Introduction to
the Theory of Computation by Michael Sipser.
- Exercise 2.13 on page 121 of Introduction to
the Theory of Computation by Michael Sipser.
- What would happen if the first production in that grammar were replaced by S --> T?
- Can you give a pushdown automaton that recognizes the language
generated by the grammar in exercise 2.13?
- [Programming Exercise] Write a simulator for pushdown automata
in your favourite programming language. The program should allow the
user to input an automaton to be simulated, and the input on which to
carry out the simulation. It should also be possible to save automata,
and load already saved ones.