CS 3156 Section C, Fall 1998
Homework 4 -- due Monday, Nov. 2

1. Give context-free grammars that generate the following languages over the alphabet tex2html_wrap_inline26 :

(a) tex2html_wrap_inline28 , i.e., the language of palindromes over tex2html_wrap_inline26 .
(b) tex2html_wrap_inline32 . Hint: if n is even, then m must be odd; if n is odd, then m must be even.
(c) tex2html_wrap_inline42
(d) tex2html_wrap_inline44

2. Prove the following: if L is a context-free language, then tex2html_wrap_inline48 is also context-free.

3. Problem 2.14, page 121 of the book.

4. Problem 2.19, page 121 of the book.

5.

(a) Give context-free grammars that generate the languages tex2html_wrap_inline50 and tex2html_wrap_inline52 .
(b) Show that tex2html_wrap_inline54 .
(c) Use the result established in Example 2.20, page 117-118 of the text, to show that the class of context-free languages is not closed under intersection.
(d) Use (c) and DeMorgan's law (Theorem 0.10, page 20 of the text) to prove that the class of context-free languages is not closed under complementation.