CS3331程序代写、代写C/C++编程

日期：2021-12-02 09:24

CS3331 – Assignment 4

due Dec. 6, 2021

2-day no-penalty extension until: Dec. 8, 11:55pm

(SRA’s cannot be used to extend further)

1. (70pt) For each of the following languages, prove, without using Rice’s Theorem, whether it is (i)

in D, (ii) in SD but not in D, or (iii) not in SD.

(1) L1 = {| L(M) ? {a, aa}}

(2) L2 = {| L(M) ? {a, aa}}

(3) L3 = {| L(M) = {a, aa}}

(4) L4 = {| L(M) ∈ D}

(5) L5 = {| ?L(M) ∈ D}

(6) L6 = {| L(M) ∈ SD}

(7) L7 = {| ?L(M) ∈ SD}

(8) L8 = {| there exists some input w on which M performs at least one right move}.

(9) L9 = {| there exists some input w which M accepts in |w| steps or less}.

(10) L10 = {| ε ∈ L(M1) ∩ L(M2)}.

2. (30pt) For each of the languages in question 1 which is not in D, explain briefly how you would use

Rice’s Theorem to prove they are not in D.

READ ME! Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be typed but high-quality

hand-written solutions are acceptable. Make sure you submit everything as a single pdf file.

LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to

all the other programs, it is free, and you can start using it in minutes; here is an introduction:

CS3331 – Assignment 3

due Nov. 30, 2021

2-day no-penalty extension until: Dec. 2, 11:55pm

(SRA’s cannot be used to extend further)

1. (20pt) Construct a deterministic Turing machine M that, given as input a binary string w, computes

the remainder of w modulo 4. M starts with the initial configuration (s,w) and halts with the

configuration (h,(w mod 4)2). It is assumed that the input, w, is a valid nonnegative number in

base 2, that is, w ∈ {0} ∪ 1{0, 1}?.

Here are some examples of M ’s behaviour:

(s,0) `?M (h,0); (s,1011) `?M (h,11); (s,101) `?M (h,1).

Describe M using the macro language (such as the ones in Examples 17.8-9, p. 275 of textbook).

2. (40pt) Prove that the following languages are in D (if you need to define TM’s, then clear English

description is sufficient):

(a) L = {|M has 3 states},

(b) L = {|M is a TM and L(M) ∈ SD},

(c) L = {| M halts on the input w in at most 3|w| steps},

(d) L = {| M uses only at most |w| tape cells before and after the input w (maximum

3|w| tape cells in total)}.

3. (20pt) Can you build a Turing machine that enumerates all encodings of Turing machines whose

language is not empty? Explain your answer.

4. (10pt) Given a language L that is not decidable (that is, L 6∈ D) and a context-free language C,

what can you say about the decidability of L ∪ C? Explain your answer.

5. (10pt) Consider the closure, SDc, of SD under complement, union, and intersection. Because SD

is not closed under complement, we have that SD ( SDc. We have obtained therefore a class of

languages, SDc, that is strictly larger than SD. Does this contradict Church’s thesis? Explain your

answer.

READ ME! Submit your solution as a single pdf file on owl.uwo.ca. Solutions should be typed but high-quality

hand-written solutions are acceptable. Make sure you submit everything as a single pdf file.

LATEX: For those interested, the best program for scientific writing is LATEX. It is far superior to

all the other programs, it is free, and you can start using it in minutes; here is an introduction: