Solved CS 331: Theory of Computing Problem Set 5

Description

Problem 1 (20 points)
Let Σ = {0, 1}. Consider the following language over Σ:
L = { w ∈ Σ
∗
| w contains twice as many 0’s as 1’s }.
(10 points) Describe in pseudo-code (as in Example 3.7 in the
textbook) of a Turing machine M that recognizes L .
(10 points) Formally define M. You may write down a formal
definition or draw a diagram like Figure 3.8 in the textbook. You may
choose Γ freely.
2 / 6
CS 331: Theory of Computing
Problem 2 (20 points)
Let Σ = {0, 1} and Γ = {0, 1, , #, x} (where denotes white
space). Write a Turing machine M such that given any input
w ∈ Σ
∗
, M halts with tape content w#w
R .
(10 points) Describe M in pseudo-code.
(10 points) Formally define M. You may write down a formal
definition or draw a diagram like Figure 3.8.
Note: we do not care if M halts in accepting state or rejecting
state.
3 / 6
CS 331: Theory of Computing
Problem 3 (20 points)
Let M = hΣ, Γ, Q, q0, δ, qaccept , qrejecti be a Turing machine where
Σ = {0, 1}, Γ = {0, 1, } ( denotes white space),
Q = {q0, q1, q2, q3, qaccept , qreject}, and δ is represented by the
following table.
δ 0 1
q0 (q0, 0, R) (q0, 1, R) (q1, , L)
q1 (q2, 1, L) (q1, 0, L) (q3, 1, L)
q2 (q2, 0, L) (q2, 1, L) (qaccept , , R)
q3 − − (qaccept , , R)
(10 points) Show the sequence of computation of M when given
input 01101.
(10 points) What is the functionality of M. Justify your answer.
4 / 6
CS 331: Theory of Computing
Problem 4 (20 points)
Let L be a language over Σ = {0, 1}. We order finite words in L
by length, and for words of the same length, we order them
lexicographically. Prove that L is Turing-decidable if and only if L
can be enumerated by an enumerator Turing machine in strictly
increasing order.
Note: Your proof should consists of two parts, each of which is
worth 10 points.
5 / 6
CS 331: Theory of Computing
Problem 5 (20 points)
A 2-PDA is a 6-tuple hQ, Σ, Γ, δ, q0, Fi, where Q, Σ, Γ, and F are all finite
sets, and
Q is the set of states,
Σ is the input alphabet,
Γ is the stack alphabet,
δ : Q × Σ × Γ × Γ → P(Q × Γ × Γ) is the transition function,
q0 ∈ Q is the start state, and
F ⊆ Q is the set of accept states.
Basically, a 2-PDA is a PDA that operates on two tapes simultaneously.
For example, (q
0
, b1, b2) ∈ δ(q, σ, a1, a2) means the machine goes from q
to q
0 when it reads letter σ, and the symbol a1 (resp. a2) is on the top of
the stack 1 (resp. stack 2). And it replaces a1 (resp. a2) with b1 (resp. b2).
Prove that any Turing machine can be simulated by a 2-PDA.
Hint: Can a Turing machine configuration be represented by two stacks?