## Topics

• Decision Problems
• Context free grammars.

## 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