Example Of Turing Machine

Example 1

Design a TM to recognize all strings consisting of an odd number of α’s. Solution:-

The Turing machine M can be constructed by the following moves −

Let q1 be the initial state.

1)If M is in q1; on scanning α, it enters the state q2 and writes B (blank).

2)If M is in q2; on scanning α, it enters the state q1 and writes B (blank).

From the above moves, we can see that M enters the state q1 if it scans an even number of α’s, and it enters the state q2 if it scans an odd number of α’s.

Hence q2 is the only accepting state.

 

Example 2

Design a Turing Machine that reads a string representing a binary number and erases all leading 0’s in the string. However, if the string comprises of only 0’s, it keeps one 0.

Solution:-

Let us assume that the input string is terminated by a blank symbol, B, at each end of the string.

The Turing Machine, M, can be constructed by the following moves −

Let q0 be the initial state.

1) If M is in q0, on reading 0, it moves right, enters the state q1 and erases 0. On reading 1, it enters the state q2 and moves right.

2) If M is in q1, on reading 0, it moves right and erases 0, i.e., it replaces 0’s by B’s. On reaching the leftmost 1, it enters q2 and moves right. If it reaches B, i.e., the string comprises of only 0’s, it moves left and enters the state q3.

 3) If M is in q2, on reading either 0 or 1, it moves right. On reaching B, it moves left and enters the state q4. This validates that the string comprises only of 0’s and 1’s.

4) If M is in q3, it replaces B by 0, moves left and reaches the final state qf.

5) If M is in q4, on reading either 0 or 1, it moves left. On reaching the beginning of the string, i.e., when it reads B, it reaches the final state qf.

 

 

Contributor's Info

Created:
2Comments
Bharath Sathuri @bharathsathuri
18 Oct 2019 09:18 am
please simplify example 2
Rohit Panwar @panwarrohit
18 Oct 2019 08:50 pm
@Sathuri Bharath Kumar Goud can you plz tell me what you exactly wants ? bcz this is just an example of tuning machine.