Ars Digita University
Theory of Computation
Recitation 5 , 05/09/01

Topics

Problems to work on

Decision Problems

  1. Finish the decision problems form the last recitation handout.

CFG warmup

  1. Give a context free grammar that generates the language of palindromes {w(0+1+epsilon)wR | w is in (0 + 1)*}
  2. Give a context free grammar that generates every possible string over {0,1}
  3. Give a context free grammar that generates the language 0n1 0n 111 0m 1r   where n, m, r >= 0
  4. Give a context free grammar that generates the language of all strings that contain 101.
  5. Give a context free grammar that generates the language of all strings with an equal number of zeros and ones.

And/Or

  1. Give a context free grammar that generates the language that has equal numbers of 0's and 1's or contains 101.
  2. Give a context free grammar that generates the language that has equal numbers of 0's and 1's and contains 101.

Complements

  1. Give a context free grammar that generates the language of all strings of the form 0m1n where n >= m >= 0.
  2. Give a context free grammar that generates the language of all strings of the form 0m1n where n > m >= 0.
  3. Give a context free grammar that generates the complement of the language 0*1*.
  4. Give a context free grammar that generates the language { w | w is not equal to 0n1n for any choice of n}
  5. Challenging problem: Give a context free grammar that generates the language { w | w is not a palindrome}

Dimitri Kountourogiannis, dimitrik@alum.mit.edu