1 Convert CFG to PDA (10+15 points)

Consider the language L = {1nD1m |n ≤ m}

a

Construct a CFG for L

b

Convert the CFG into a PDA

2 Construct PDA (20 points)

Consider the language L over the alphabet Σ = {a,b} which contains at least twice as many a’s than b’s. Construct a PDA to recognize L.

3 Pumping lemma CFG (20 points)

Show that the language L = {ss|s ∈ Σ* } is not a context free language.

4 TM details and overview (15 + 15 points)

a

Consider the turing machine in the state xxxQ0 1111#00000#xxx1111. Essen- tially an equal number of xs are there at the beginning and post the 2nd  while there are a bunch of 0s in between the s.  Give detailed turning machine transi- tions to go to the state xxxx111#00000#xxxxP0111.  Essentially cross off the corresponding 1s with xs.

b

Give a turning machine recognizing L = {1n #0p #1n #0q #1n   |n,p,q ≥ 0}