0
0
Turing machine
Question 1
Design a Turing machine for the following languages:
a. A = {am b” c” | m,n >=0} www
b. B = {a” b” cm | m,n >=0}
Answer
a. Turing machine for language A = {am b” c” | m,n >=0} www:
- Start at the beginning of the input tape with the read/write head on the leftmost cell.
- Scan the input tape from left to right to check if the input string is in the form of am b” c” www.
- Count the number of “a”s by moving right on the tape until a “b” is encountered.
- If there is no “b” after all the “a”s, then the input string is not in the language A. Reject the input and halt.
- If a “b” is found, move right on the tape until a “c” is found.
- If there is no “c” after all the “b”s, then the input string is not in the language A. Reject the input and halt.
- If a “c” is found, move right on the tape until the end of the string.
- If the end of the string is reached and there are no more “w”s, accept the input string and halt.
- If there are more “w”s, repeat the process starting from step 3.
Turing machine for language A = {am b” c” | m,n >=0} www:
Q = {q0, q1, q2, q3, q4, q5}
Σ = {a, b, c, w}
Γ = {a, b, c, w, X}
δ : Q × Γ → Q × Γ × {L, R}
q0 is the start state, q5 is the accept state, and q3 and q4 are the reject states.
δ(q0, a) = (q0, a, R)
δ(q0, b) = (q1, X, R)
δ(q1, b) = (q1, b, R)
δ(q1, c) = (q2, X, R)
δ(q2, c) = (q2, c, R)
δ(q2, w) = (q3, w, L)
δ(q3, c) = (q3, c, L)
δ(q3, b) = (q4, b, L)
δ(q4, a) = (q4, a, L)
δ(q4, X) = (q0, X, R)
δ(q4, w) = (q5, w, R)
b. Turing machine for language B = {a” b” cm | m,n >=0}:
- Start at the beginning of the input tape with the read/write head on the leftmost cell.
- Scan the input tape from left to right to check if the input string is in the form of a” b” cm.
- Count the number of “a”s by moving right on the tape until a “b” is encountered.
- If there is no “b” after all the “a”s, then the input string is not in the language B. Reject the input and halt.
- If a “b” is found, move right on the tape until the end of the string.
- Count the number of “c”s by moving left on the tape until a “b” is encountered.
- If there is no “b” after all the “c”s, then the input string is not in the language B. Reject the input and halt.
- If a “b” is found, move left on the tape until the beginning of the string.
- If there are any remaining “a”s or “c”s on the tape, reject the input and halt.
- If there are no more “a”s or “c”s on the tape and the read/write head is on the leftmost cell, accept the input string and halt.
Turing machine for language B = {a” b” cm | m,n >=0}:
Q = {q0, q1, q2, q3, q4, q5}
Σ = {a, b, c}
Γ = {a, b, c, X}
δ : Q × Γ → Q × Γ × {L, R}
q0 is the start state, q5 is the accept state, and q3 and q4 are the reject states.
δ(q0, a) = (q0, a, R)
δ(q0, b) = (q1, X, R)
δ(q1, b) = (q1, b, R)
δ(q1, c) = (q2, X, L)
δ(q2, c) = (q2, c, L)
δ(q2, b) = (q3, b, L)
δ(q3, X) = (q3, X, L)
δ(q3, a) = (q3, a, L)
δ(q3, b) = (q3, b, L)
δ(q3, c) = (q4, X, R)
δ(q4, c) = (q4, c, R)
δ(q4, b) = (q5, b, R)
Question 2
c. C = {a^ib^Jc^k | i,j,k >= 0 and i+ j =k}
d. D = {a^ib^jc^k | i,j,k >= 0 and i+ k = j}
Answer
Turing machine for language C = {a^ib^jc^k | i,j,k >= 0 and i+ j =k}:
Q = {q0, q1, q2, q3, q4, q5}
Σ = {a, b, c}
Γ = {a, b, c, X, Y}
δ : Q × Γ → Q × Γ × {L, R}
q0 is the start state, q5 is the accept state, and q3 and q4 are the reject states.
δ(q0, a) = (q0, a, R)
δ(q0, b) = (q1, X, R)
δ(q1, b) = (q1, b, R)
δ(q1, c) = (q2, Y, R)
δ(q2, c) = (q2, c, R)
δ(q2, X) = (q3, X, L)
δ(q3, a) = (q3, a, L)
δ(q3, Y) = (q3, Y, L)
δ(q3, b) = (q3, b, L)
δ(q3, X) = (q3, X, L)
δ(q3, a) = (q4, a, L)
δ(q4, X) = (q4, X, L)
δ(q4, a) = (q4, a, L)
δ(q4, Y) = (q4, Y, L)
δ(q4, b) = (q5, b, R)
Turing machine for language D = {a^ib^jc^k | i,j,k >= 0 and i+ k = j}:
Q = {q0, q1, q2, q3, q4, q5, q6}
Σ = {a, b, c}
Γ = {a, b, c, X, Y}
δ : Q × Γ → Q × Γ × {L, R}
q0 is the start state, q6 is the accept state, and q4 and q5 are the reject states.
δ(q0, a) = (q0, a, R)
δ(q0, b) = (q1, X, R)
δ(q1, b) = (q1, b, R)
δ(q1, c) = (q2, Y, L)
δ(q2, b) = (q2, b, L)
δ(q2, X) = (q3, X, R)
δ(q3, b) = (q3, b, R)
δ(q3, Y) = (q3, Y, R)
δ(q3, c) = (q4, c, L)
δ(q4, a) = (q4, a, L)
δ(q4, X) = (q5, X, L)
δ(q5, a) = (q5, a, L)
δ(q5, b) = (q5, b, L)
δ(q5, Y) = (q2, Y, L)
δ(q2, c) = (q6, c, R)
Question 3
e. E = {a^nb^mc^md^n,m,n >=1}
f. F = {a^ib^jc^k |l,j,k >= 0 and i = j or l=k}
Answer
Turing machine for language E = {a^nb^mc^md^n,m,n >=1}:
Q = {q0, q1, q2, q3, q4, q5, q6}
Σ = {a, b, c}
Γ = {a, b, c, X, Y}
δ : Q × Γ → Q × Γ × {L, R}
q0 is the start state, q6 is the accept state, and q4 and q5 are the reject states.
δ(q0, a) = (q1, X, R)
δ(q1, a) = (q1, a, R)
δ(q1, b) = (q2, Y, R)
δ(q2, b) = (q2, b, R)
δ(q2, c) = (q3, c, R)
δ(q3, d) = (q3, d, R)
δ(q3, X) = (q4, X, L)
δ(q4, a) = (q4, a, L)
δ(q4, Y) = (q4, Y, L)
δ(q4, b) = (q4, b, L)
δ(q4, c) = (q5, c, L)
δ(q5, d) = (q5, d, L)
δ(q5, X) = (q0, X, R)
Turing machine for language F = {a^ib^jc^k |l,j,k >= 0 and i = j or l=k}:
Q = {q0, q1, q2, q3, q4, q5}
Σ = {a, b, c}
Γ = {a, b, c, X, Y}
δ : Q × Γ → Q × Γ × {L, R}
q0 is the start state, q5 is the accept state, and q3 and q4 are the reject states.
δ(q0, a) = (q1, X, R)
δ(q0, b) = (q2, Y, R)
δ(q1, a) = (q1, a, R)
δ(q1, Y) = (q3, Y, L)
δ(q2, b) = (q2, b, R)
δ(q2, X) = (q4, X, L)
δ(q3, Y) = (q3, Y, L)
δ(q3, c) = (q5, c, R)
δ(q4, X) = (q4, X, L)
δ(q4, a) = (q5, a, R)
δ(q5, a) = (q5, a, R)
δ(q5, b) = (q5, b, R)
δ(q5, Y) = (q0, Y, R)
Greetings! Very useful advice in this particular article! Its the little changes that will make the biggest changes. Thanks for sharing!