1
$\begingroup$

$L = \{a^n b^n c^n ... d^n | n>0 \}$

so for example $L = \{a^n b^n | n>0 \}$ , $L = \{a^n b^n c^n| n>0 \}$ and such

can the turing machine accept these in O(n)? if yes then what about a better time complexity like O(logn) or O(1)?

my take on this is: yes because we can use n number of tapes and we go through all of them word by word altogether, but a book i was reading said the best time is $O(n^2)$ so i got confused, maybe it was referring to standard turing machine but idk

so my question is this :

  1. can a turing machine do this in O(n) ?

  2. if yes, then is there a better time complexity?

$\endgroup$
  • $\begingroup$ You use $n$ for two things. I assume that in $O(n)$ (not $o(n)$, which has a different meaning), $n$ is the input length. A simple adversary argument shows that you have to read the entire input before you can be sure that the input belongs to $L$, so you cannot do it in $O(\log n)$ on a Turing machine (or even on a RAM machine). $\endgroup$ – Yuval Filmus Mar 25 '18 at 11:48
4
$\begingroup$

Yes a TM with multiple head for example can easily do this. for $a^nb^n$ you can have two heads one at the first occurence of A's and other at the first occurence of B. Then at each iteration you can cross each off. If both see blank accept. If A head does not see A or B head does not see a B reject. Else cross both off with some special character.

Clearly this takes one linear pass in time O(N). Now for the lower bound. It is not possible to do with less than O(N). If you use N number of tapes by definition then it is $\Omega{(N)}$. If you use K number of tapes then it is $K \times (N/K)$ which is still O(N). The reason for this lower bound is that you have check each character since any one character can break the rule of this language. Thus we get a linear lower bound.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.