Courses

# Designing of Turing Machines Computer Science Engineering (CSE) Notes | EduRev

## Computer Science Engineering (CSE) : Designing of Turing Machines Computer Science Engineering (CSE) Notes | EduRev

The document Designing of Turing Machines Computer Science Engineering (CSE) Notes | EduRev is a part of the Computer Science Engineering (CSE) Course Theory of Computation.
All you need of Computer Science Engineering (CSE) at this link: 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={an|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 q0 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,
δ(q0, a) = (q1, a, R)

In state q1, 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 q0, and
3. moves to the next cell on the right side.

The corresponding transition function is,
δ(q1, a) = (q0, a, R)

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

Transition table for the TM is, Consider the processing of string, aaa using the above TM,  The TM halts at state q1. qis a final state. So the string aaa is accepted.

Consider the processing of string, aaaa using the above TM,  The TM halts at state q0. qis not a final state. So the string aaaa is not accepted.

Example 2:
Design a turing machine over {a} to accept the language L={an|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
q0 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,
δ(q0, a) = (q1, a, R)

In state q1, 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 q0, and
3. moves to the next cell on the right side.
The corresponding transition function is,
δ(q1, a) = (q0, a, R)

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

Transition table for the TM is, Consider the processing of string, aaaa using the above TM,  The TM halts at state q0. qis a final state. So the string aaaa is accepted.

Example 3:
Design a Turing machine over {a, b} to accept the language L={anbn|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 q0 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 q0 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, q0 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. δ(q0, a) = (q1, #, R)

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

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

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

5. In state q4, 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. δ(q4, b) = (q4, b, L)
b. If the head is pointing to symbol a, then symbol ’a’ remains unchanged, state q4 changes to state q5, and head moves to cell on the left side. δ(q4, a) = (q5, a, L)
c. If the head is pointing to symbol #, then symbol ’#’ remains unchanged, state q4 changes to state q6, and head moves to cell on the right side. δ(q4, #) = (q6, #, R). This indicates that all a’s have been cancelled.
In state q4, head simply passes over all the b’s of the input string from right to left and changes to state q5 as soon as symbol a is received.

6. In state q5, head does the following:
a. If the head is pointing to input symbol a, then symbol ’a’ remains unchanged, state q5 remains unchanged, and head moves to next cell on the left side. δ(q5, a) = (q5, a, L)
b. If the head is pointing to symbol #, then symbol ’#’ remains unchanged, state q5 changes to state q0, and head moves to cell on the right side. δ(q5, #) = (q0, #, R)
In state q5, head simply passes over all the a’s of the input string from right to left and changes to state q0 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 q6 and moves to final state where it halts and it indicates that the string is accepted.

8. In state q6, 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. δ(q6, #) = (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 q6 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 q0 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 q0, then head enters state q1, and if symbol ’b’ is received, then head enters state q2.

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={anbncn|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 q0 and head points to first symbol, a in the string. a is replaced with a #, changes state to q1, and moves towards right.
2. In state q1, 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 q2, and again moves towards right.
3. In state q2, 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 q3, and turns back towards left.
4. In steps 1-3, each symbol ’a’ is matched with the corresponding symbols ’b’ and ’c’. In state q3, 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 q4.
5. In state q4, head reads symbol ’a’, replaces it with a #, changes to state q1and 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 q4. This shows that all a’s were replaced with #’s. Now if the string is valid, no ’b’ should be available in state q4.
7. In state q4,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 q4 to indicate the rejection of the string.
If no ’b’ is encountered, and if symbol ’y’ is obtained, then it changes state to q5, and moves towards right.
8. In state q5,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 q5 to indicate the rejection of the string.
If no ’c’ is encountered, and if symbol ’#’ is obtained, then it changes state to qf , and moves towards left.
9. In state qf , 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 = {0n|n is a multiple of 3}.
2. Design a TM that accepts the language L = {anb2n|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)*}

Offer running on EduRev: Apply code STAYHOME200 to get INR 200 off on our premium plan EduRev Infinity!

## Theory of Computation

18 videos|44 docs|39 tests

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

,

;