CSE 237, Fall 2017
Practice Midterm


        Closed-book, closed notes, turned-off smartphones. 

        Problems may be done in any order.  Start each problem on top of new page, and show your work.

        You have 1 hour 15 minutes to do five problems (15 minutes per problem).  Pace yourself!

        Good luck!


FOR EXTRA CREDIT, PLEASE HAND IN YOUR SOLUTION PROBLEM 6 (ONLY) at the beginning of class on Monday October 16. Donít forget to write your name on it.





We have the following two languages over the alphabet {0,1}:

L1 = {0m 1 0n 1 : where m, n 0 and m < n}

L2 =  {0m 1 0n 1 : where m, n 0 and m+n is divisible by 2}


(a)    What is the shortest string in L1?  What about L2?

(b)   Describe the language L1  L2. What is the shortest string in L1  L2



Consider the language for the regular expression (a a*) b | a b

(a) Is this language infinite or not?  Please justify your answer in one sentence.

(b) Is it equivalent to a* b?  Please justify your answer in one sentence.

(c) Find a simple NFA accepting this language; try to make it as simple as possible.



(a) One of the languages in Problem 1 is NOT regular. Which one? Prove it.

(b) What is a different way to prove that itís not regular? (You don't have to give a complete proof, but give enough details so I know what the proof would be)

(c) Is it context free? Justify your answer.



Let G = <V, Σ, R, S> be the following grammar:

     S -> T | H

†††† T-> epsilon | X X T

†††† H -> epsilon | X X X H

†††† X -> 0

(a) What is V? What is Σ?  What is the size of R?

(b) Show the parse tree in G for 000000

(c) Is this grammar ambiguous?  Justify your answer. Hint: consider the string above.



(a) Let L be the set of strings generated by G from problem 4. Describe L in English.

(a) Create PDA M that accepts L, without using the algorithm that converts a CFG to a PDA. Show the diagram for M; name your states and number your transitions.

(b) Show a computation in M for 00, as a sequence of configurations (state, remaining input, stack contents), with arrows between them labeled with transition numbers. 

Hint: to make sure your PDA is correct, check that it accepts everything thatís in L, and does not accept anything thatís not in L.



(a)   Prove that {an bm an bm |  n, m >= 0} is not context free, using the context-free pumping lemma.

(b)   Recall that an intersection of a context-free language and a regular language is always context-free. 
Use this fact, together with the result from part (a), to show that the language L0 = {ww | w is a string over {a,b,c}} is not context-free. 

Note: in class, we proved that L0 is not context free using the Pumping Lemma; this is an alternate way to prove it.