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, w) and halts with the configuration (q, w), 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, w), 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, (w − 1)(2)) or (h, 0), 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,)|−∗ (h,0)
(s,000)|−∗ (h,0)
(s,01)|−∗ (h,0)
(s,111)|−∗ (h,110)
(s,001100)|−∗ (h,1011)
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′ = {< M > | M accepts exactly 2 strings}.
Can you tweak the Turing machine you described in part (a) to semidecide L′?
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.