Turing machine for Regular languages in theory of automata

By: Prof. Dr. Fazal Rehman | Last updated: December 28, 2023

Turing machine for Regular languages

Regular languages can be represented through finite automata and similarly can be represented through Turing Machine.

This machine must accept all strings starting from a and ending with b. e.g, ab,aab, abab etc.

Let’s discuss the diagram;

Start:

Starts the machine

a,a,R:

Read a from input tape and write a and move Right on input tape.

State 2: 

Read a from input tape and write a and move Right on input tape. There is a loop of a, a, R on state 2. 

If read b from input tape, then write b and move right and halts the machine by accepting the string.

If there is any a on accept state then again control moves to the state 2, enforcing the machine to not end with a.

Turing machine Diagram

Demo of Turing machine Execution 

Question: String ab can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer:

Yes, this string can be read by the Turing machine in the Path of machine execution is mentioned below.

Path: start > 2 > accept.

Question: String ba can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer: Sorry this string can’t be read by this Turing machine because this machine only can read the strings that are started with alphabet a

Question: String abbba can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer:

Answer: Sorry this string can’t be read by this Turing machine because this machine only can read the strings ended with alphabet b.

Path: start > 2 > accept > accept > accept > 2. Here, 2 is the ending state but actual ending state is “accept”.

Question: String ababab can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer:

Yes, this string can be read by the Turing machine in the Path of machine execution is mentioned below.

Path: start > 2 > accept > 2 > accept > 2 > accept.

 

Question: String abbbb can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer:

Yes, this string can be read by the Turing machine in the Path of machine execution is mentioned below.

Path: start > 2 > accept > accept > accept > accept.

 

Question: String baabbb can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer: Sorry this string can’t be read by this Turing machine because this machine only can read the strings that are started with alphabet a.

 

Question: String aababb can be ready by this Turing machine or not? If it can be read then what will be the path?

Answer: Yes, this string can be read by the Turing machine in the Path of machine execution is mentioned below.

Path: start > 2 > 2 > accept > accept > accept.

 

Read More Examples of Turing Machine

1. Turing Machine to copy a string: with animations
2. Turing Machine of numbers divisible by 3: with animations
3. Turing machine for anbncn: with animations

4. Turing machine of two equal binary strings: with animations

5. Turing Machine to Accepts palindromes: with animations

6. Turing machine for a’s followed by b’s then c’s where the number of a’s multiplied by the number of b’s and equals to the number of c’s: with animations

7. Turing machine to Add two binary numbers: with animations

8. Turing machine to  Multiply two unary numbers: with animations
9. Turing machine to Multiply two binary numbers: with animations
10. Turing Machine for the complement of a string
11. Turing Machine for the language of aⁿbⁿ where a=b.
12. Turing Machine for a is less than b, a^mbⁿ where a=b or m=n.

13. Turing machine for the language of all those string in which a is less than b