0
$\begingroup$

Consider the following language:

$$L=\{a^nb^n | n \ge 1\}$$

I constructed the following Turing Machine:

\begin{eqnarray} T &=& (Q, \Sigma, \Gamma, \delta, q_0, B, F) \nonumber \\ Q &=& \{q_0, q_1, q_2, q_3, q_4\} \nonumber \\ \Sigma &=& \{a, b\} \nonumber \\ \Gamma &=& \{a, b, X, Y, B\} \nonumber \\ F &=& \{q_4\} \nonumber \end{eqnarray}

enter image description here

enter image description here

When the input comes as $aabb$, the Turing Machine works like this:

enter image description here

How can you know the time complexity of this Turing Machine?

$\endgroup$
2
  • $\begingroup$ "how it works" does not mean the transition diagram… I meant describe the steps with words in english. $\endgroup$
    – Nathaniel
    Apr 25 at 10:37
  • $\begingroup$ @Nathaniel I editted it. $\endgroup$
    – t24akeru
    Apr 25 at 11:04
2
$\begingroup$

If I correclty understand the algorithm, your TM starts "marking" the first $a$, then it finds the first $b$ and marks it, then it comes back the the first unmarked $a$ and so on. So, assuming that you have in input a string $w$ of lenght $n$ that belongs to the language $L$, you have $\frac{n}{2}$ $a$'s that have to match with the same number of $b$, each $a$ is paired to a $b$ that is $\frac{n}{2}$ cells away, so to perform a complete matching you need $\frac{n}{2}$ transitions from an $a$ to reach the $b$ to be coupled with it, and again $\frac{n}{2}$ transitions to reach the next $a$, so in total $n\cdot \frac{n}{2}$ transitions (actually, you have to perform an extra transition for each letter to put the head in the right place, so the exact amount of transitions is $\frac{n^2}{2}+n+1=O(n^2)$).

Now, let us consider a word $w$ of lenght $n$ that does not belong to the language $L$. If it start with $b$, it is immediately rejected, so suppose $w=a^hb^kv$, where $v\in a\Sigma^*$ has lenght $j>0$ and $h+k+j=n$. If $k\leq h$, then the TM will performs $\frac{k^2}{2}+k+1$ transitions before stopping (and rejecting $w$), while if $k>h$, then it will make $\frac{h^2}{2}+h+1$ transitions. So, the worst case correspond to the maximum of the function $$ f(h,k,j)=\cases{\frac{k^2}{2}+k+1, \quad k\leq h\\ \frac{h^2}{2}+h+1,\quad k> h} $$ on the constraint $h+k+j=n$, $j>0$, and it is not difficult to see that it is reached for $|h-k|=1$ and $j=1$.

Summing up: the worst case is reached when $w$ belongs to the language $L$, and the TM must carry out $O(|w|^2)$ transitions.


If you want to play with your TM and see the exact number of transitions, go here, compile and load a word, enjoy!

$\endgroup$
2
  • $\begingroup$ Thank you so much! It is so helpful $\endgroup$
    – t24akeru
    Apr 26 at 2:54
  • $\begingroup$ So the time complexity is $\Theta(n^2)$. It is also $O(n^3)$, $\Omega(n)$, and so on. $\endgroup$ Apr 26 at 14:45

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.