Turing Machine for a is smaller than b in theory of automata

Last modified on August 4th, 2020

Let us begin with Turing Machine for a is less than b, ambn where a=b or m=n.

Turing Machine for 0's are less than 1's
Figure: Turing Machine for a’s are less than b’s

Logic:

If machine reads anyone a from the input tape, then machine write X and if machine reads any b then machine write y;

a = X

b = Y

in the end, the machine must read Y, write Y, and move right as illustrated in the diagram(start to state 4).

After that, there are multiple b’s to enforce that b’s are larger in number and a’s are smaller in number.

Turing Machine a is Smaller than b
Turing Machine a is Smaller than b

Video Lecture with full of Animations

Accepted strings:

Such kind of strings should be accepted by Turing Machine.

e.g, abB, aabbbb, aaabbbbb,…..etc.

Rejected strings:

Such kind of strings should be rejected by Turing Machine.

e.g, ab, aab, aaabb,…..etc.

Subscribe for Friendship

Latest posts by Prof. Fazal Rehman Shamil (see all)