Theory of Computation

Recitation 6, 05/10/01

- Rigorous proofs using the pumping lemma.
- More constructions with context free grammars.
- Chomsky Normal Form.

- Finish working on the CFG problems from the lst handout.
- (Warmup). Generate the grammar for 0*1(0+1)*.
- Using the grammar above, What are the leftmost and rightmost derivation for the strings 1001, 0011? What are the parse trees?
- (Text 2.13) Consider the following grammar.
S --> TT | U T --> 0T | T0 | 1 U --> 0U00 | 1

Describe the language it generates.

- Put the following grammar in Chomsky Normal form. (Text 2.14)
A --> BAB | B | epsilon B --> 00 | espilon

- Put the following grammar in Chomsky Normal form.
A --> BAB | B | BC B --> 00 | epsilon C --> AA

- Prove that the language { x
^{2n}| n >= 0 } is not regular. - Show that the set of all strings of zeros that have length that is a perfect cube can not be described by a regular expression.

Dimitri Kountourogiannis, dimitrik@alum.mit.edu