CSE 237, Homework 7 (Proving languages non-regular)

Dina Q Goldin
Due 3/22/06

Please start each problem on a separate piece of paper.

Note: this homework must be handed in on time, to allow proper review for the midterm.

Problem 1. Simple PDAs

(a) Are the PDAs in figures 2.15 and 2.19 simple?  Explain why or why not.  If not, convert them to simple PDAs, that have as few states as possible.

(b) Let M be the PDA corresponding to figure 2.15 .Convert M to a CFG G_M, using the procedure discussed in class (also in book, p.120).  Simplify G_M so it does not have any "useless" rules.

(c) For w = "0011", show both the computation of M on w (as a sequence of configurations) and the leftmost derivation of w in G_M.

Problem 2. Applying CFL pumping lemma

(a) Do problem 2.30 (b) from textbook.  Note: the solution is in the textbook, so do not hand it in.

(b) Prove that {0ⁿ 1^m 0ⁿ 1^m |  n, m >= 0} is not context free, using the context-free pumping lemma.

Problem 3. Applying CFL closure properties

As we know, the intersection of a context-free language and a regular language is always context-free. Use this fact, together with the result you proved in problem 2(b), to show that the following language L is not context-free:

L = {ww | w is a string over {0,1}}

Note: as we discussed in class, it can also be proved with the pumping lemma;  this is an alternate approach.