CS3331程序辅导、辅导C/C++编程
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: