编译原理辅导 | CS3331 – Assignment 3 Decidable and Semi-Decidable Languages

这次作业是用图灵机设计决定性和半决定性语言

CS3331 – Assignment 3 – 2018
Decidable and Semi-Decidable Languages I
Due: Tuesday, Nov 27, 2018 (Latest to submit: Friday, Nov 30)
1. (20pt) Construct a deterministic Turing machine M that decides the language
L = {w ∈ {a, b}
∗
| w has ab as a substring and ends with ba}.
M starts with the initial configuration (s, 2w) and halts with the configuration (q, 2w), for the appropriate
q ∈ {y, n}. Describe M in detail using a directed graph whose edges are labelled by transitions (such as
the one in Example 17.2, p. 368 of textbook).
2. (20pt) Construct a deterministic Turing machine M that subtracts one from its binary input if it is positive
and sets it to zero if its input is zero. This machine computes the function
f(n) = (
0 if n is 0
n − 1 otherwise
M starts with the initial configuration (s, 2w), where w ∈ {0, 1}
∗
; the binary input w is interpreted as an
integer number. The machine must remove all leading zeros from the input and halt in the appropriate
configuration (h, 2(w − 1)(2)) or (h, 20), where w(2) is the binary representation of w. If w = ε, treat it
as a representation of 0. Here are some examples of M s behaviour:
(s, 2)|−∗
(h, 20)
(s, 2000)|−∗
(h, 20)
(s, 201)|−∗
(h, 20)
(s, 2111)|−∗
(h, 2110)
(s, 2001100)|−∗
(h, 21011)
Describe M using the macro language (such as the one in Example 17.8, p. 377 of textbook).
3. (20pt) Construct a deterministic Turing machine M that multiplies two unary numbers. Specifically, given
the input string < x >;< y >, where < x > is the unary encoding of a natural number x and < y > is
the unary encoding of a natural number y, M should output < z >, the unary encoding of z = xy. For
example, on input 111;1111, M should output 111111111111. Describe M using the macro language
4. (20pt) Consider the language L = {< M > | M accepts at least two strings}.
(a) Describe in clear English a Turing machine M that semidecides L.
(b) Suppose we changed the definition of L just a bit. We now consider:
L
0 = {< M > | M accepts exactly 2 strings}.
Can you tweak the Turing machine you described in part (a) to semidecide L
0
?
5. (20pt) Describe in clear English a Turing machine that semidecides the language
L = {< M > | M accepts the binary encodings of the first four Fibonacci numbers}.
2
Note well: You may submit your assignment in one of two ways:
◦ Ideally, submit your solution as a pdf file on OWL (scanned written assignments are fine). Assignments
submitted this way will not be accepted after 11:59 pm on November 30.
◦ Otherwise staple your assignment and hand in solutions in class or to the 3331 dropbox (locker
#306, across from the elevator on the 3rd floor of Middlesex College). Assignments submitted this way
will not be accepted after 5:00 pm on November 30.