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) set B = max{ |t| | (A,t) ∈ R}|NT| + 1 set p = the smallest prime ≥ B let u = 1p if u ∉ L(G) then let u' = u, otherwise get v,w,x,y,z from the pumping lemma for for CFGs set m = |v| + |x| + |z| 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 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 = {aⁿbⁿcⁿ | 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!