Ars Digita University
Theory of Computation
Recitation 7, 05/11/01

Topics

Problems to work on

  1. Give a grammar for the language {ai bj | i <= j <= 2i}.
  2. 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.
  3. Construct a PDA for {0n1n | n >= 0} without looking at your notes.
  4. Construct a PDA for {0n1m0m1n | n,m >= 0}

Dimitri Kountourogiannis, dimitrik@alum.mit.edu