Turing Machines: Questions
- Consider the Turing machine with input alphabet {a,b}, start state q0 and the following transitions:
| State |
Symbol |
d(State,Symbol) |
q0 |
# |
(q1,#,R) |
q1 |
a |
(q1,a,R) |
| q1 |
b |
(q1,b,R) |
| q1 |
# |
(q2,#,L) |
| q2 |
a |
(q3,#,R) |
| q2 |
b |
(q5,#,R) |
| q2 |
# |
(q2,#,Y) |
| q3 |
# |
(q4,a,R) |
| q4 |
a |
(q4,a,R) |
| q4 |
b |
(q4,b,R) |
| q4 |
# |
(q7,a,L) |
| q5 |
# |
(q6,b,R) |
| q6 |
a |
(q6,a,R) |
| q6 |
b |
(q6,b,R) |
| q6 |
# |
(q7,b,L) |
| q7 |
a |
(q7,a,L) |
| q7 |
b |
(q7,b,L) |
| q7 |
# |
(q2,#,L) |
- What is the final configuration if the input is #ab#?
- What is the final configuration if the input is #baa#?
- Describe what the Turing machine does for an arbitrary input string in {a,b}*.
- Consider the Turing machine with input alphabet {a,b}, start state q0 and the following transitions:
| State |
Symbol |
d(State,Symbol) |
q0 |
a |
(q1,A,R) |
q0 |
b |
(q1,B,R) |
| q0 |
A |
(q4,A,L) |
| q0 |
B |
(q4,B,L) |
| q0 |
# |
(q0,#,Y) |
| q1 |
a |
(q1,a,R) |
| q1 |
b |
(q1,b,R) |
| q1 |
A |
(q2,A,L) |
| q1 |
B |
(q2,B,L) |
| q1 |
# |
(q2,#,L) |
| q2 |
a |
(q3,A,L) |
| q2 |
b |
(q3,B,L) |
| q3 |
a |
(q3,a,L) |
| q3 |
b |
(q3,b,L) |
| q3 |
A |
(q0,A,R) |
| q3 |
B |
(q0,B,R) |
| q4 |
A |
(q4,a,L) |
| q4 |
B |
(q4,b,L) |
| q4 |
< |
(q5,<,R) |
| q5 |
a |
(q7,A,R) |
| q5 |
b |
(q6,B,R) |
| q5 |
# |
(q5,#,Y) |
| q6 |
a |
(q6,a,R) |
| q6 |
b |
(q6,b,R) |
| q6 |
B |
(q8,#,L) |
| q6 |
# |
(q6,#,R) |
| q7 |
a |
(q7,a,R) |
| q7 |
b |
(q7,b,R) |
| q7 |
A |
(q8,#,L) |
| q7 |
# |
(q7,#,R) |
| q8 |
a |
(q8,a,L) |
| q8 |
b |
(q8,b,L) |
| q8 |
A |
(q5,A,R) |
| q8 |
B |
(q5,B,R) |
| q8 |
# |
(q8,#,L) |
- Trace the execution of this Turing machine for the input string abaa.
- Trace the execution of this Turing machine for the input string abab.
- Describe the language accepted by this Turing machine.
- Construct a Turing machine to accept the language {aibj | i < j}
- Construct a Turing machine to accept the language {w Î {a,b}* | w contains the same number of a's as b's}
- Construct a Turing machine to accept the language {w Î {a,b}* | w = wR}
- Construct Turing machines to compute the following functions (assume that the number x is in unary notation):
- f(x) = x + 2
- f(x) = 2x
- f(x) = x mod 2
- Construct a Turing machine to implement a "shift machine" as described in the lecture notes.
- Show that every context-sensitive language is recursive (hint: how long can derivations be?)
- Consider the following unrestricted grammar:
S -> ABCS
S -> Z
CA -> AC
BA -> AB
CB -> BC
CZ -> Zc
CZ -> Yc
BY -> Yb
BY -> Xb
AX -> Xa
X -> e
Give a derivation of the sentence aaabbbccc. What is the language generated by this grammar?
- Show that the following functions are primitive recursive:
- factorial(n) = n!
- gcd(m,n) = the greatest common divisor of m and n