Name: ____________________________________________________ Alpha: _____________________

Describe help received: _________________________________________________________________

Problem 1

Complete the following proof that the language L of all strings over {0,1} whose length is prime is not a context free language. (You may want to actually do problem 2 first!)

Input: Grammar G = (Σ,NT,R,S)
Output: String u' such that u' ∈ L but u' ∉ L(G) or u' ∉ L but u' ∈ L(G)
  1. set B = max{ |t| | (A,t) ∈ R}|NT| + 1
  2. set p = the smallest prime ≥ B
  3. let u = 1p
  4. if u ∉ L(G) then let u' = u, otherwise
    1. get v,w,x,y,z from the pumping lemma for for CFGs
    2. set m = |v| + |x| + |z|
    3. if m ≠ 1 set u' = vwmxymz else set u' = vw0xy0z
 
Proof of correctness for algorithm: (note: 0 and 1 are not prime!)

Problem 2

Apply the algorithm given above to the grammar
S → SS | SSS | 00 | 01 | 11 | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111
 

Problem 3

Read the section in the lecture notes "Another mystery algorithm", which we didn't get to in class, but which shows that the intersection of a CFL and a regular language is a CFL. Basically we have an intersection algoirithm for 1 PDA and 1 NDFA. So why can't we intersect two PDA's? Essentially because we'd need another stack! Draw machine that is like a PDA with two stacks that accepts the language L = {anbncn | n ≥ 0}. In the drawing, that means that each transition has a pop-symbol for stack 1 and another for stack 2; a push-symbol for stack 1 and another for stack 2. Make clear in the drawing how I'm supposed to interpret your transitions!