CS 411: Automation and Computation

pick any three problems to submit for your homework.

1) Show that the language of bitstrings of the form w1w^R or w0w^R isnt regular. (Recall, w^R means the string w written backwards.) Notice these bitstrings are palindromes of odd length.

2) Consider that language of bitstrings that either have even length (e.g. 100101) or are not palindromes (e.g. 10011). This language cannot be regular given the result of question 1. Explain why.

3) Show that the language in question 2 is context free.

4) Give a CFG for bitstrings that contain twice as many 0's as 1's.

5) Give a CFG for bitstrings with zero or more 0s followed by at least as many 1s.

6) Give a CFG for bitstrings with at least two 0s.

7) Give a CFG for bitstrings not containing 01. (This is easier than it seems.)

8) Give a CFG for bitstrings with 2k 1s followed by 3k 0s, where k 0.

9) Draw a PDA for your CFG in #8

10) Give a CFG for bitstrings of the form 0ⁿ1^m0^n+m, where m 1, m 1.

11) Draw a PDA for your CFG in #10