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?
Custom Work, Just for You!
Can’t find the tutorial you need? No worries! We create custom, original work at affordable prices! We specialize in Computer Science, Software, Mechanical, and Electrical Engineering, as well as Health Sciences, Statistics, Discrete Math, Social Sciences, Law, and English.
Custom/Original Work Essays cost as low as $10 per page.
Programming Custom Work starts from $50.
Get top-quality help now!