Question

Give turing Machine for L= a*i b*2j a*i b*2j where i,j>=0. Also provide the logic, show 1 or 2 strings for accept, reject .

Answer 1

given turing machine is:

L=a*i b*2j a*i b*2j

this is easy to understand if we take one example:

L=abbabb L

1 2 3 4 5 6

blank

a

b

b

a

b

b

blank

let say our pointer is on index 1 check the element which is 'a' put the 'X' on its place then our resultant sequence will be

1 2 3 4 5 6

blank

X

b

b

a

b

b

blank

Now move the pointer to right until you don't find 'a' when you find it replace it with 'X'

1 2 3 4 5 6

blank

X

b

b

X

b

b

blank

as we find 'a' and we replaced it with "x" now again move toward left until you don't find X when you find "x" move one step in right direction and u will find b replace it with 'Y' again move in right direction until you don't find 'b' replace it with "Y" too.

similar steps we need to repeat our resultant sequence will be:

1 2 3 4 5 6

blank

X

Y

Y

X

Y

Y

blank

it will traverse completely.

it means above language is accepted by given turning machine.

if we use example abba it will rejected by turning machine.

For the case of "aa" we will start from left from B ie blank as we do move toward right and try to find b if u don't find b but blank it means there is not any b in the language all the character are "a" just replace them with X. Similarly in case of "bbbb" as start from blank first character encountered is b it means there is not "a" just put all b as Y