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).
Solution:
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).
Solution:
❑ R 1L h
❑R 1L
R❑L 1L❑
0L❑
❑
0
0
0
1
1
1
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 = ∅.
1
In each case, describe M using the macro language.
Solution:
(a) The machine accepts a and loops for any other input:
R R a
b,❑
❑
y
R
a,b
(b) This is impossible. A machine semideciding Σ∗ would accept everything, thus deciding Σ∗
.
(c) The machine always loops, accepting nothing:
R 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} .
Solution:
TM that semidecides L:
1. Generate all binary encodings of natural numbers in lexicographical order.
2. For each number, check if it is prime and keep the primes only.
3. On input <M, run M on all primes in dovetailing mode.
4. If three computations accept, then accept.
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.)
Solution:
(a) SD is closed under intersection. To prove this, assume L1, L2 ∈ SD are arbitrary semidecidable
languages and assume they are semidecided by M1 and M2, resp. We construct M∩ that
semidecides L1 ∩ L2 as follows:
On input w
Run M1 on w
If M1 rejects, then reject
If M1 accepts, then
Run M2 on w
If M2 rejects, then reject
If M2 accepts, then accept
Another solution for M∩:
On input w
2
Run in parallel M1 on w and M2 on w
If both accept, then accept
(b) SD is closed under concatenation. To prove this, assume L1, L2 ∈ SD are arbitrary semidecidable languages and assume they are semidecided by M1 and M2, resp. We construct Mc
that semidecides L1L2 as follows:
On input w
Run in parallel, in dovetailing mode:
For each w = w1w2, w1, w2 ∈ Σ
∗
Run M1 on w1 and M2 on w2
If both accepts, then accept
Another solution for Mc:
On input w
Nondeterministically guess a factorization w = w1w2, w1, w2 ∈ Σ
∗
Run in parallel M1 on w1 and M2 on w2
If both accepts, then accept
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.
Solution:
(a) Yes. Consider TM ML that always loops. Then <ML6∈ Hany. Choose L1 = Hany∪{<ML},
L2 = Hany. Since Hany is not decidable, L1 and L2 are also not decidable. But L1 − L2 = {<
ML} is finite, hence regular; and nonempty.
(b) Yes. Choose L1 = Hany ∪ {<ML}, L2 = ¬Hany. Then L1 ∪ L2 = {<M | M is a TM} is
decidable but L1 6= ¬L2.
Note Submit your solution as a (typed) pdf file on owl.uwo.ca.
3