Ars Digita University
Theory of Computation
Recitation 6, 05/10/01

Topics

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

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

Rigorous pumping lemma proofs

Problems from previous handouts kindly reproduced here. Rigorously prove using the pumping lemma.
  1. Prove that the language { x2n | n >= 0 } is not regular.
  2. 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