代做CS 3800 Spring 2024 Homework 10代做留学生SQL语言

日期：2024-04-08 11:18

CS 3800-Online

Homework 10 (due Friday, April 5)

Spring 2024

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.

(c) The textbook gives a proof that ETM  is recognizable (Exercise 4.5 page 211, solution page 213). This solution is based on the methods of lecture 20a (using clocks).  Give another proof based on the methods of lecture 20 and the possibility to encode computations (computation histories) as strings.

8.  [4 Points] Tint-two-way.  Design a two-way Turing machine with input alphabet {0, 1} that on input any binary number bin(x) (the binary representation of x ∈  N) outputs bin(x + 1). The machine starts with bin(x) written on an otherwise empty tape with the head under the first symbol and ends in state qaccept  with bin(x+1) written anywhere on

this otherwise empty tape with the head under the first symbol.

Note: to run your program on a two way machine:

– in tint-generator, select the option Two-way TM

–  in tint, enter a command such as

./tint -m two-way-tm -t -v my-program.txt ''101111''

9.  [6 Points] Tint-two-way.  Design a two-way Turing machine with input alphabet {0, 1} that on input a string

bin(x)

(where bin(x) is the binary representation of x ∈ N) outputs bin(3x).  The machine starts with bin(x) written on an otherwise empty tape with the head under the first symbol and ends in state qaccept  with the output bin(3x) written anywhere on this otherwise empty tape and the head under the first symbol.

For example, on input 101 the machine outputs 1111, on input 1 the machine outputs 11, and on input 11 the machine outputs 1001.

10.  [0 Point] Exercise 4.5 page 211.  Solution page 213.  Let

ETM  = {⟨M⟩  |  M is a TM and L(M) = ∅} .

Show that ETM , the complement of ETM  is Turing-recognizable.

Do not submit.

11.  [0 Point] Do not submit.  Problem 4.10 page 211.  The solution is in the book page 213, this is for practice only.

12.  [0 Point] Do not submit.  Problem 4.12 page 211.  The solution is in the book page 214, this is for practice only.

13.  [0 Point] Do not submit.  Problem 4.14 page 211.  The solution is in the book page 214, this is for practice only.