CS3331 – Assignment 3

CS3331 – Assignment 3

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.