Instructions: This homework is to be submitted on GradeScope as a single  pdf (not in parts) by 11:59 pm on the due date.  You may either type your solutions in a word processor and print to a pdf, or write them by hand and submit a scanned copy.  Do write and submit your answers as if they were a professional report.  There will be point deductions if the submission isn’t neat (is disordered, difficult to read, scanned upside down, etc....).

Begin by reviewing your class notes, the slides, and the textbook.  Then do the exercises below.

Show your work. An unjustified answer may receive little or no credit.

Read: 5.1 through p219, 5.3, 6.3 (for Tuesday) and 5.2 (for Friday)

1.  [4  Points]  Length  of  Chomsky  derivations.    Find  a  context-free  grammar  G  in Chomsky normal form and a word w  E L(G) of length  |w|  =  n  >  0  such that some derivation of w in G has length equal to the maximum bound 2n(n + 1) - 1 calculated in lecture 21.

2.  [6 Points] Length of Chomsky derivations.  The context-free grammar ({S,A, B}, {a,b},R, S) whose productions are:

S 一 AA

A 一 AB

A 一 a

B 一 b

is in Chomsky normal form.

For the string w = abba, what is the minimum length of derivations of w  (in the sense of lecture 21)?

3.  [10 Points] Encodings.  Consider the Turing machine T whose encoding〈T）is

011 000 110 000 011 111 110 111 100 011 000 110 111 011 000 110 000 001 011 000 110 111 000 011 000 110 111 000 010

(a)  Decode the machine and write its transitions.

(b) What is L(T)?

For each of the following questions, give a yes/no answer and explain your answer.

(c)  Is T a decider?

(d) Is T E ATM  ?

(e) Is〈T）E ATM

(f) Is T E Self-ATM  ?

(g) Is〈T）E Self-ATM  ?

4.  [10 Points] A tough machine.  Prove that there exists a fixed Turing machine M0  with input alphabet Σ = {0, 1} such that the language

{w ∈ Σ*  |  M0  accepts w}

is undecidable.

5.  [10 Points] Undecidable  language.  For each n ∈  N let Mn  be some Turing machine with input alphabet {0, 1} and consider the language

A = {bin(n) |  n ∈ N and Mn  rejects bin(n)}

where bin(n) is the binary representation of number n.  That is, bin(n) is in A if and only if the computation of Mn  on input bin(n) terminates in the reject state.

(a)  Prove that A is not decided by any of the machines in the list M0 , M1 , M2 , M3 , . . . .

(b) Where (be very specific) would your argument from part (a) fail if you tried to prove that A isn’t recognized by any of the machines in the list?

6.* [10 Points] Diagonalization Let Σ = {0, 1} and let A ⊆ Σ*  be alanguage whose words are encodings of Turing machines each of which is a decider.  That is, each word in A has the form ⟨M⟩ where M is a decider.

In this problem, you are to show that if A is recognizable, then there is a decidable language B ⊆ Σ*  that isn’t decided by any of the deciders whose encodings are in A.

(a)  Carefully define B. For full credit, give a formula of the form B = {··· |  ···} . (b)  Explain why B isn’t decided by any of the deciders whose encodings are in A. (c) Explain why your language B is decidable.

7.  [10 Points] Encoding Computations.  Lecture 22 will show that the language (defined over Turing machines M)

ETM  = {⟨M⟩ |  L(M) = ∅}

is undecidable. We wish to show that ETM  isn’t recognizable.  For this, it is sufficient to show that

ETM  = {⟨M⟩ |  L(M)  ∅}

is recognizable.

(a) Why is it sufficient to show that ETM  is recognizable?  Give exact references from lecture and slides.

(b) Actually, {⟨M⟩  |   L(M)  ∅}  isn’t really the complement of {⟨M⟩  |   L(M) = ∅} . Explain why it isn’t the true complement and why it doesn’t matter: give explicit references to lecture slides.