Question 1) Consider the following language L_λ = { | M does NOT accept the empty string λ}. Prove that this language is not RE.

You MUST do this via a reduction using L_nd. That is, show that if there exists an accepting TM for L_λ then an acceptor for L_nd could be built.

Remember that Lnd = { | ∉ L(M)}. Be sure to show your ProgX (AKA Mx) program that is fed into the assumed accepting TM for L_λ.

Question 2) Consider the following language. L₂ = { : 1000010 ∈ L(M)} that is the language of encodings of all TMs that accept the string 1000010. This language is RE but non-recursive. Prove this by first describing in English a machine to accept L₂ and then reducing L_d to L₂. Note: L_d = { | ∈ L(M)} machines that accept their own encoding.

To solve this problem assume a recursive TM exists for L2 (one that halts on all inputs) and show how to construct a recursive TM for Ld using it. Again, be sure to show your Mx program contents.

Question 3) Describe a TM that solves the following acceptance problem. Provide a brief but complete English description of how the machine works.

L = { a^Nb^M | N,M >= 1 and M > N }

Question 4) What programX would you use to prove that the following language is undecidable? (undecidable is the same as not Recursive). That is, show me the program you would need to perform a reduction.

L = { | L(M) is Recursive but neither Regular nor Context-Free}

Question 5) Draw the transition diagram for a TM that accepts the following language L = { w | w contains twice as many 1's as 0's}. Please briefly describe HOW your machine operates in a general sense.

Question 6) Draw the transition diagram for a TM that accepts the following language. Briefly describe how your machine works.

L = { w | w begins and ends in the same symbol (0 or 1)}

Question 7) For each of the following languages, indicate if they are Regular, Context-free, Recursive, R.E. (Recursively Enumerable), or Non-RE. NOTE - if a language falls into more than one category then it should be placed into the most restrictive - for example, the language { 00, 11, 000, 111} is regular, context-free, recursive and R.E but regular is the most restrictive and thus that is the correct answer.

a. ∅ (empty language)

b. 0^N1^N0^N

c. WW | W ∈ (0 + 1 )*

d. WW^R | W ∈ (0 + 1 )* and WR is W in reverse

e. | 0000 ∈ L(M)

f. | L(M) is a CFL

g. ∑*

h. L = { w | w ∈ ( 0 + 1 )* AND |w| ≤ 7 }

i. W | W == W^R (language of palindromes)

j. | ∉ L(M)