**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.

__________________________________________________________________________

** **

**PROBLEM 1.**

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

*L _{1}* = {

*L _{2}* = {

(a) What is the
shortest string in *L _{1}*? What about

(b) Describe the
language *L _{1 ∩}*

** **

**PROBLEM 2.**

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

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

** **

**PROBLEM 3.**

(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.

**PROBLEM 4.**

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**.**

**PROBLEM 5.**

(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.

**PROBLEM 6. **

**(a)
**Prove
that {**a**^{n}** b ^{m} a**

**(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
L_{0} = {*ww* | *w* is a string
over {**a**,**b**,**c**}}
is not context-free.

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