Turing machine recognizing language $L=\{a^ib^{i-j}c^j|i>j\ge1\}$

118 Views Asked by At

I am having some trouble with designing a Turing machine that recognizes the language:

$L=\{a^ib^{i-j}c^j\big|i>j\ge1\}$

For example, word accepted by TM: $w=aaaaabbccc$

To be more precise, I don't know how to check that number of b is $i-j$.

Just simple explanation would be very helpful.

1

There are 1 best solutions below

0
On

Now I see a serious mistake I did. I assumed that number of 'c' must be greater than number of 'b', which is wrong.

So the solution for this is overwrite 'a' and 'b' with 'X' for each 'b' then overwrite 'a' and 'c' with 'X' for each 'c'. If there are only 'X' characters then the word is accepted.