## 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!