Designing of Turing Machines - Theory of Computation - Computer Science Engineering (CSE)

Part II. Designing of Turing Machines

3 Designing of TM

Following are the basic guidelines for designing a TM.
1. The fundamental objective of scanning a symbol in the tape is to know what to do in the future. TM must remember the past symbols scanned. TM can remember this by going to the next unique state.
2. The number of states must be minimised. This is achieved by changing the states only when there is a change in the written symbol or when there is a change in the movement of the head.

Following examples show designing of TMs.

Example 1:
Design a turing machine over {a} to accept the language L={aⁿ|n is odd}.
The initial instant of the TM is shown below. The input tape contains aaa followed by blanks. The TM is initially in state q₀ and head points to the first a of the input string w.

The working of the TM is as follows:
In state q0, head reads symbol a from the current cell and
1. keeps the contents of the current cell as a,
2. changes state of the TM to q1, and
3. moves to the next cell on the right side.
The corresponding transition function is,
δ(q₀, a) = (q1, a, R)

In state q₁, head reads symbol a from the current cell and
1. keeps the contents of the current cell as a,
2. changes the state of the TM to q₀, and
3. moves to the next cell on the right side.

The corresponding transition function is,
δ(q₁, a) = (q₀, a, R)

Thsi process continues till a blank symbol, # is reached.
If the blank symbol is reached in state q₁, it indicates that input string contains an odd number of a’s.
If the blank symbol is reached in state q₀, it indicates that input string contains an even number of a’s.
Hence, q₁ is the final state.

Transition table for the TM is,

Consider the processing of string, aaa using the above TM,

The TM halts at state q₁. q₁ is a final state. So the string aaa is accepted.

Consider the processing of string, aaaa using the above TM,


The TM halts at state q₀. q₀ is not a final state. So the string aaaa is not accepted.

Example 2:
Design a turing machine over {a} to accept the language L={aⁿ|n is even}. The initial instant of the TM is shown below. The input tape contains aaaa followed by blanks. The TM is initially in state
q₀ and head points to the first a of the input string w.

The working of the TM is as follows:
In state q₀, head reads symbol a from the current cell and
1. keeps the contents of the current cell as a,
2. changes state of the TM to q₁, and
3. moves to the next cell on the right side.
The corresponding transition function is,
δ(q₀, a) = (q₁, a, R)

In state q₁, head reads symbol a from the current cell and
1. keeps the contents of the current cell as a,
2. changes the state of the TM to q₀, and
3. moves to the next cell on the right side.
The corresponding transition function is,
δ(q₁, a) = (q₀, a, R)

Thsi process continues till a blank symbol, # is reached.
If the blank symbol is reached in state q₀, it indicates that input string contains an even number of a’s.
If the blank symbol is reached in state q₁, it indicates that input string contains an odd number of a’s.
Hence, q₁ is the final state.

Transition table for the TM is,

Consider the processing of string, aaaa using the above TM,


The TM halts at state q₀. q₀ is a final state. So the string aaaa is accepted.

Example 3:
Design a Turing machine over {a, b} to accept the language L={aⁿbⁿ|n ≥ 1 }.
Example strings in this language are ab, aabb, aaabbb, aaaabbbb,.........
Let the string be aaaabbbb.
String recognition process of the Turing machine is as follows:
Initially, TM is in state q₀ and head points to first a in the string.

1. Read the first symbol a of the string and convert this a to blank (#).
2. The head keeps moving towards right till the input string is crossed and the first blank symbol after the string is reached.
3. From this #, turn one cell left and reach the last symbol of the input string. If it is 1, convert it to #. After performing the first three steps, input tape with aaaabbbb###, will contain #aaabbb####. That is, leftmost a is cancelled with rightmost b.
4. Now after converting the last b to #, the head keeps moving towards left till a # is reached, turn towards right and converts the first available a to #, and keeps moving towards right till a # is reached. It then turns left and converts the first available b to # and keeps moving towards left. After step 4, input tape will contain ##aabb#####. This marks the cancellation of the next leftmost a by the next rightmost
b.
5. The head keeps repeating step 4 till all the a’s are cancelled by teh corresponding b’s.
6. If the cancellation process is successfully completed, then the string is accepted.
7. If there are remaining uncancelled a’s or b’s, then the input string is not accepted.

Transition table corresponding to the TM is given below:

The working of the above TM is explained below:
1. The head reads the first symbol of the input string in state q₀ and does the following:
a. If the symbol is # or b, then TM halts. If the first symbol is #, then it is a null string and does not belong to the language. If the symbol is ’b’, then it is also an invalid string. Thus, q₀ is a non-final state.
b. If the first symbol is ’a’, then head converts this input symbol to #, changes state to q1, and moves towards right. δ(q₀, a) = (q₁, #, R)

2. In state q₁, head does the following:
a. If the head is pointing to input symbol a, then symbol ’a’ remains unchanged, state q₁ remains unchanged, and head moves to next cell on the right side. δ(q₁, a) = (q₁, a, R)
b. If the head is pointing to input symbol b, then symbol ’b’ remains unchanged, state q₁ changes to state q₂, and head moves to next cell on the right side. δ(q₁, b) = (q₂, b, R)
In state q₁, head simply passes over all the 0s of the input string from left to right and changes to state q₂ as soon as symbol b is received.

3. In state q₂, head does the following:
a. If the head is pointing to input symbol b, then symbol ’b’ remains unchanged, state q₂ remains unchanged, and head moves to next cell on the right side. δ(q₂, b) = (q₂, b, R)
b. If the head is pointing to symbol #, then symbol ’#’ remains unchanged, state q₂ changes to state q₃, and head moves to cell on the left side. δ(q₂, #) = (q₃, #, L)
In state q₂, head simply passes over all the b’s of the input string from left to right and changes to state q₃ as soon as symbol # is received and turns towards left.

4. In state q₃, head does the following:
a. If the head is pointing to input symbol b, then symbol ’b’ is replaced with #, state q₃ changes to q₄, and head moves to next cell on the left side. δ(q₃, b) = (q₄, #, L)
In state q₃, symbol ’b’ is replaced with # in response to the ’a’ symbol replaced with # in state q₀.

5. In state q₄, head does the following:
a. If the head is pointing to input symbol b, then symbol ’b’ remains unchanged, state q4 remains unchanged, and head moves to next cell on the left side. δ(q₄, b) = (q₄, b, L)
b. If the head is pointing to symbol a, then symbol ’a’ remains unchanged, state q₄ changes to state q₅, and head moves to cell on the left side. δ(q₄, a) = (q₅, a, L)
c. If the head is pointing to symbol #, then symbol ’#’ remains unchanged, state q₄ changes to state q₆, and head moves to cell on the right side. δ(q₄, #) = (q₆, #, R). This indicates that all a’s have been cancelled.
In state q₄, head simply passes over all the b’s of the input string from right to left and changes to state q₅ as soon as symbol a is received.

6. In state q₅, head does the following:
a. If the head is pointing to input symbol a, then symbol ’a’ remains unchanged, state q₅ remains unchanged, and head moves to next cell on the left side. δ(q₅, a) = (q₅, a, L)
b. If the head is pointing to symbol #, then symbol ’#’ remains unchanged, state q₅ changes to state q₀, and head moves to cell on the right side. δ(q₅, #) = (q₀, #, R)
In state q₅, head simply passes over all the a’s of the input string from right to left and changes to state q₀ as soon as symbol # is received.

7. In steps 1-6, leftmost a and rightmost b cancel out each other. This is done by converting them to blanks. This is repeated till all the a’s are cancelled by the corresponding b’s.
When all a’s are cancelled by the respective b’s, head will point ot a # symbol in state q₆ and moves to final state where it halts and it indicates that the string is accepted.

8. In state q₆, head does the following:
a. If the head is pointing to input symbol #, then it indicates that all the a’s have been successfully matched with the corresponding b’s. Hence the TM changes state to qf and halts.It indicates taht the string is accepted. δ(q₆, #) = (qf , #, R)
b. If the head is pointing to symbol b, this shows that the number of b’s is more than the number of a’s and hence the TM halts in state q₆ to indicate the non-acceptance of the string.
Let the input string is aaabbb.
TM processes the string as follows:


After the 14th step leftmost a is cancelled with the rightmost b. This process is repeated and finally we get all #s and TM will reach state qf . Then the string aaabbb is accepted by the above TM.

Example 4:
Design a Turing machine over {a, b} to accept the language L={wwR|w ∈ (a, b)⁺ }.
Example strings in this language are aa, abba, bb, baab, ababbbbaba, ........

String recognition process of the Turing machine is as follows:
1. Initially, TM is in state q₀ and head points to first symbol in the string.
2. The symbol may be a or b. Aftyer reading this symbol, this symbol is replaced with a # and keeps moving towards right till the whole of the string is crossed and the first # after  the string is reached.
3. From this blank, the head turns one cell left and reaches the last symbol of the input string. If this symbol matches with the first symbol of the input string, it converts it into a #.
4. Steps 1-3 match the first and last symbols of the input string. If this matching is successful, the head traverses back and crosses the string to reach the first #. From this #, it turns towards right and matches the leftmost and rightmost symbols of the remaining string. If the matching is successful, then the symbols are converted to #s.
5. The process repeats till the symbols are matched.
6. To keep track of the symbol to be matched, if symbol ’a’ is received in state q₀, then head enters state q₁, and if symbol ’b’ is received, then head enters state q₂.

Transition table corresponding to the Turing machien is given below:

Let the input string is abaaba.
TM processes the string as follows:








 Example 5:
Design a Turing machine over {a, b, c} to accept the language L={aⁿbⁿcⁿ|n ≥ 1 }.
Example strings in this language are abc, aabbcc, aaabbbccc, aaaabbbbcccc, ....

String recognition process of the Turing machine is as follows:
1. Initially, TM is in state q₀ and head points to first symbol, a in the string. a is replaced with a #, changes state to q₁, and moves towards right.
2. In state q₁, the head continues to move towards right till all the a’s are passed over and the first ’b’ is obtained. Now ’b’ is replaced with ’x’, changes state to q₂, and again moves towards right.
3. In state q₂, the head continues to move towards right till all the b’s are passed over and the first ’c’ is obtained. Now ’c’ is replaced with ’y’, changes state to q₃, and turns back towards left.
4. In steps 1-3, each symbol ’a’ is matched with the corresponding symbols ’b’ and ’c’. In state q₃, head continues to move towards left and passes over the whole string to reach the blank symbol, #. At #, it turns right and changes state to q₄.
5. In state q₄, head reads symbol ’a’, replaces it with a #, changes to state q₁and moves towards right.
6. Now steps 1-3 are repeated to match the symbols a, b and c. this process continues till the symbol ’x’ is obtained in state q₄. This shows that all a’s were replaced with #’s. Now if the string is valid, no ’b’ should be available in state q₄.
7. In state q₄,head continues to move towards right till all the x’s are passed over and no symbol, ’b’ is obtained. If ’b’ is found, it indicates a mismatch in the number of ’a’ and ’b’ symbols. TM halts in state q₄ to indicate the rejection of the string.
If no ’b’ is encountered, and if symbol ’y’ is obtained, then it changes state to q₅, and moves towards right.
8. In state q₅,head continues to move towards right till all the y’s are passed over and no symbol, ’c’ is obtained. If ’c’ is found, it indicates a mismatch in the number of ’a’ and ’c’ symbols. TM halts in state q₅ to indicate the rejection of the string.
If no ’c’ is encountered, and if symbol ’#’ is obtained, then it changes state to q_f , and moves towards left.
9. In state q_f , TM halts to indicate the acceptance of the string.
Transition table for the TM is shown below:

Exercises:
1. Design a TM that accepts the language L = {0ⁿ|n is a multiple of 3}.
2. Design a TM that accepts the language L = {aⁿb2ⁿ|n > 0}.
3. Design a TM over {a,b,c} to accept the language L = {wcw|w ∈ (a|b)*}.
4. Design a TM over {a,b} to accept the language L = {ww|w ∈ (a|b)*}