Topics

• Decision Problems
• Context free grammars.

Problems to work on

Decision Problems

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

CFG warmup

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

And/Or

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

Complements

9. Give a context free grammar that generates the language of all strings of the form 0^m1ⁿ where n >= m >= 0.
10. Give a context free grammar that generates the language of all strings of the form 0^m1ⁿ where n > m >= 0.
11. Give a context free grammar that generates the complement of the language 0*1*.
12. Give a context free grammar that generates the language { w | w is not equal to 0ⁿ1ⁿ for any choice of n}
13. Challenging problem: Give a context free grammar that generates the language { w | w is not a palindrome}