Is $L=\{\,a^ib^jc^k \mid i=2j=3k\, \}$ a Turing language?

194 Views Asked by At

Is $L= \{a^ib^jc^k \mid i=2j=3k\}$ a Turing language?

At first I thought it was possible to scan the tape and for each $c$ delete the amount of $a$ by the amount of $b$, it works when the input is $aaaaaabbbcc$ but if the input is $aaaaaaaaaaaabbbbbbcccc$ it is not.

How can I figure it out the algorithm, which technique can I use to solve this?

1

There are 1 best solutions below

0
On

A simple way to solve your question is to start with the context-sensitive language $C= \{a^nb^nc^n \mid n \geqslant 0\}$ and use the fact that the class of context-sensitive languages is closed under non-erasing morphisms. Now, consider the non-erasing morphism $f$ defined by $f(a) = a^6$, $f(b) = b^3$ and $f(c) = c^2$. Then $$f(C) = \{a^{6n}b^{3n}c^{2n} \mid n \geqslant 0 \} = L.$$ Thus $L$ is context-sensitive.