CSC173: Homework 3.1
Turing Machines
1. Let M = ⟨Q,Σ , Γ,δ, q0 , q accept , qreject ⟩, where
Q = {q0 , q accept , qreject }
Σ = {a, b}
Γ = {a, b, ⊔}
and δ is given by the following table:
|
q σ
|
δ(q,γ)
|
|
q0
q0
q0
|
a
b
⊔
|
q0
q0
q accept
|
b
a
⊔
|
R
R
R
|
(a) Draw M’s transition function as a state diagram.
(b) Trace the computation of M on input aabbbaa.
(c) Describe informally (in English) what M does.
2. Let M = ⟨Q,Σ , Γ,δ, q0 , q accept , qreject ⟩, where
Q = {q0 , q1 , q accept , qreject }
Σ = {a}
Γ = {a, ⊔}
and δ is given by the following diagram:
(a) Give M’s transition function as a table.
(b) Trace the computation of M on inputs aa and aaa.
(c) Describe informally (in English) what M does.
3. Trace the execution of the machine M2 from Sipser Example 3.7 on each of the following inputs:
(a) 0
(b) 00
(c) 000
(d) 000000
4. Trace the execution of the machine M1 from Sipser Example 3.9 on each of the following inputs:
(a) 11
(b) 1#1
(c) 1##1
(d) 10#11
(e) 10#10
5. Design and write the formal definition of a Turing machine with input alphabet {a, b} that scans to the right until it finds two consecutive a’s and then accepts.
(a) Does your machine halt on all inputs?
(b) If not, could you design one that does halt on all inputs?
(c) Can this language, the set of strings that contain two consecutive a’s, be decided by a simpler type of machine (that we have seen in this class)?