Theory of Computation

Recitation 7, 05/11/01

- Using regular expressions and context free grammars with Lex and Yacc to build complex programs quickly. A calculator example.
- Chomsky Normal Form (Finish problems on Chomsky Normal Form
that we didn't get to last time,

i.e. all of them ;-) - Push Down Automata.

- Give a grammar for the language {a
^{i}b^{j}| i <= j <= 2i}. -
Consider the grammar
S --> z A s A --> xb B yz B --> cd A q | epsilon

Play around with this grammar and try to guess what a pumping lemma for CFG's might look like. - Construct a PDA for {0
^{n}1^{n}| n >= 0} without looking at your notes. - Construct a PDA for {0
^{n}1^{m}0^{m}1^{n}| n,m >= 0}

Dimitri Kountourogiannis, dimitrik@alum.mit.edu