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
Monday, 24 February 2003 at 10:15 in A4-106.
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?