# 编译原理辅导 | 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.