Homework 7

CS 3810 – Summer 2008

1. Use the pumping lemma for regular sets to show that { ww^R | w ∈ (a+b)* } is not a regular set.

2. Design a PDA to accept the language { w ∈ (a+b)* | w contains twice as many a's as b's }

3. Design a PDA to accept the language { aⁱb^jc^k | i = j or j = k }

4. Let L = { aⁿbⁿaⁿbⁿ | n≥1 }. Show that L can be expressed as the intersection of two context-free languages.

5. Write a cfg for the set of all strings of balanced parentheses. The parentheses must be properly nested. Some sample strings in the language are (()()), ((()(()()))), ()()()(), etc.

6. Exercise 7.1.3 [Chomsky Normal Form]