首页 » 图灵机辅导 » 图灵机辅导 | CS3331 – Assignment 3 due Nov. 26, 2019,

图灵机辅导 | CS3331 – Assignment 3 due Nov. 26, 2019,

这个assignment是使用图灵机解决几个练习题
CS3331 – Assignment 3
due Nov. 26, 2019, (latest to submit: Nov. 29, 11:55pm)
1. (10pt) Consider the alphabet Σ = {a, b, c} and define the function succ : Σ∗ → Σ

, succ(w) is the
word immediately following w in lexicographic order. Construct a deterministic Turing machine M
that computes the function succ, that is, M starts with the initial configuration (s, w) and halts
with the configuration (h, succ(w)). Describe M in details using a directed graph whose edges
are labelled by transitions (such as the one in Example 17.2, p. 268 of textbook).
2. (10pt) Construct a deterministic Turing machine M that adds one to its binary input if it is even
and subtracts one if it is odd. M starts with the initial configuration (s, w), where w ∈ {0, 1}

;
the binary input w is interpreted as an integer number. Possible leading 0’s have to be removed as
well. The machine halts in the appropriate configuration (h, (w ± 1)(2)), where w(2) is the binary
representation of w.
Here are some examples of M’s behaviour:
(s, ) `

(h, 1)
(s, 000) `

(h, 1)
(s, 01) `

(h, 0)
(s, 111) `

(h, 110)
(s, 001100) `

(h, 1101)
Describe M using the macro language (such as the one in Example 17.8, p. 275 of textbook).
3. (20pt) Construct a Turing Machine M that semidecides, but does not decide, each of the following
languages over the alphabet Σ = {a, b}:
(a) L1 = {a},
(b) L2 = Σ∗
,
(c) L3 = ∅.
In each case, describe M using the macro language.
4. (20pt) Describe in clear English a Turing machine that semidecides the language
L = {< M >| M accepts the binary encodings of at least 3 prime numbers} .
5. (20pt) Is the set SD closed under:
(a) Intersection?
(b) Concatenation?
Prove your answers. Clear English description of any Turing machines is sufficient. (That is, you
don’t have to effectively build the machine, instead explain how the machine behaves.)
6. (20pt) Let L1 and L2 be two languages that are not decidable.
(a) Is it possible that L1 − L2 is regular and L1 − L2 6= ∅? Prove your answer.
(b) Is it possible that L1 ∪ L2 is decidable but L1 6= ¬L2? Prove your answer.
Note Submit your solution as a (typed) pdf file on owl.uwo.ca.
1


程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB


本网站支持 Alipay WeChatPay PayPal等支付方式

E-mail: vipdue@outlook.com  微信号:vipnxx


如果您使用手机请先保存二维码,微信识别。如果用电脑,直接掏出手机果断扫描。

blank

发表评论

您的电子邮箱地址不会被公开。