CSE 355 Quiz 10
A Turing Machine can have a choice as to whether to move right or left on a given transition. -
ANS-False
Every CFL can be recognized by a Turing Machine - ANS-True
Every language that a Turing Machine can recognize is a CFL - ANS-False
Suppose we augmented our definition of a TM to include moving right 5 tape cells in a single
transition. Then the class of languages ordinary TMs recognize is the same as this augmented
model. - ANS-True
Every TM's starting configuration is unique - ANS-True
In a DPDA, suppose we allow only transitions that can do only one of pop, push, and read. To
break up a transition that does all three we should:
(a) Read then pop then push
(b) Read then push then pop
(c) Pop then push then read
(d) Pop then read then push
(e) Snap then crackle then pop - ANS-a
If a DPDA has the transition δ(q, a, x) = (q', y) with a ∈ Σ, x ∈ Γ, then
it can also have the transition:
(a) δ(q, (epsilon), (epsilon)) = (q', y)
(b) δ(q, (epsilon), x) = (q', y) provided x != y and y ∈ Γ
(c) δ(q, (epsilon), y) = (q', x) provided x != y and y ∈ Γ
(d) δ(q, a, (epsilon)) = (q', x)
(e) δ((epsilon), b, x) = (q', x) provided x != y and y ∈ Γ and a != b and b ∈ Σ - ANS-c
What is the smallest number of states that a TM could have?
(a) 0
(b) 1
(c) 2
(d) 3
(e) 4 - ANS-c
What is the smallest number of tape symbols that a TM with nonempty input alphabet could
have?
(a) 0
(b) 1
A Turing Machine can have a choice as to whether to move right or left on a given transition. -
ANS-False
Every CFL can be recognized by a Turing Machine - ANS-True
Every language that a Turing Machine can recognize is a CFL - ANS-False
Suppose we augmented our definition of a TM to include moving right 5 tape cells in a single
transition. Then the class of languages ordinary TMs recognize is the same as this augmented
model. - ANS-True
Every TM's starting configuration is unique - ANS-True
In a DPDA, suppose we allow only transitions that can do only one of pop, push, and read. To
break up a transition that does all three we should:
(a) Read then pop then push
(b) Read then push then pop
(c) Pop then push then read
(d) Pop then read then push
(e) Snap then crackle then pop - ANS-a
If a DPDA has the transition δ(q, a, x) = (q', y) with a ∈ Σ, x ∈ Γ, then
it can also have the transition:
(a) δ(q, (epsilon), (epsilon)) = (q', y)
(b) δ(q, (epsilon), x) = (q', y) provided x != y and y ∈ Γ
(c) δ(q, (epsilon), y) = (q', x) provided x != y and y ∈ Γ
(d) δ(q, a, (epsilon)) = (q', x)
(e) δ((epsilon), b, x) = (q', x) provided x != y and y ∈ Γ and a != b and b ∈ Σ - ANS-c
What is the smallest number of states that a TM could have?
(a) 0
(b) 1
(c) 2
(d) 3
(e) 4 - ANS-c
What is the smallest number of tape symbols that a TM with nonempty input alphabet could
have?
(a) 0
(b) 1
