Topics

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

Problems to work on

1. Finish working on the CFG problems from the lst handout.
2. (Warmup). Generate the grammar for 0*1(0+1)*.
3. Using the grammar above, What are the leftmost and rightmost derivation for the strings 1001, 0011? What are the parse trees?
4. (Text 2.13) Consider the following grammar.

   
   S --> TT | U
   T --> 0T | T0 | 1
   U --> 0U00 | 1
   
   

   Describe the language it generates.

Chomsky Normal Form

5. Put the following grammar in Chomsky Normal form. (Text 2.14)

   
   A --> BAB | B | epsilon
   B --> 00 | espilon
   
   

6. Put the following grammar in Chomsky Normal form.

   
   A --> BAB | B | BC
   B --> 00 | epsilon
   C --> AA
   
   

Rigorous pumping lemma proofs

7. Prove that the language { x²ⁿ | n >= 0 } is not regular.
8. 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.