3.5 Chapter 2

Complete the following problems:

1. (0.30) Consider the language L1 = { w | w = 1^{n/2} 0^{n/2} 1 for even n greater than 1}:

   1. (0.10) Give a CFG that generates L1.

   2. (0.05) Show the 4-tuple for the CFG.

   3. (0.05) Convert your grammar into Chomsky Normal Form. Show the steps of the proof of Theorem 2.9.

   4. (0.10) Design a PDA for the result of the CNF transform and give its 6-tuple.

2. (0.10) Convert the DFA from Chapter 1, Sections 1.1-1.2.1 into a CFG and show the 4-tuple.

3. (0.20) Design a PDA (and shows its 6-tuple) for the language L2 = { w | w ∈ {a,b}* and w contains at least 2 bs}.

4. (0.25) Prove that the language L3 = { 0^n 1^{2n} 0^{n/2} | n ≥ 0, n ∈ Z, n (mod 2) = 0} is not context-free.

5. (0.15) Do problem 2.15 from the textbook (pg 156). This is the one about a counter-example to a particular strategy for showing the context-free languages are closed under star.