1
$\begingroup$

As in, I have to design a determenistic (one-taped) turing machine that accepts that language (All strings made up of 0 and 1, where the j-th character from the end is a 0, and $j$ is a constant that we know what it is before running the machine) in less steps than the trivial steps.

In the trivial solution, I would first check if the starting point is a blank, if so the machine denies. If not, go to the last bit (first blank) then move $j$ steps to the left and check if it is $0$. All of that takes $1 + n + j$ steps, but my professor says there is a better runtime that I should come up with.

Any hints would help!

|cite|improve this question
$\endgroup$
  • $\begingroup$ You can do this in $n$ steps. Instead of going to the end of the input and counting back $k$ characters, remember what you saw in the past and use your memory to accept or reject when you reach the end of the input. $\endgroup$ – David Richerby Dec 29 '13 at 10:26
3
$\begingroup$

There is a Turing machine operating in time $n + 1$ or so, but with lots of states. The machine simulates a DFA for your language. It has $O(2^k)$ states which "remember" the last $k$ characters.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I know that the DFA for this has $O(2^k)$ states using the rank rule. But how would I remember the last $k$ characters? the machine can't guess when the $k$ characters start! $\endgroup$ – TheNotMe Dec 29 '13 at 7:38
  • 3
    $\begingroup$ I'll let you sleep on that. $\endgroup$ – Yuval Filmus Dec 29 '13 at 7:40
  • 2
    $\begingroup$ More generally, every DFA can be simulated by a Turing machine running in time $n$ or $n+1$ or so (depending on the exact model). Since your language is regular, there is a DFA for it. That's all you need to know. $\endgroup$ – Yuval Filmus Dec 29 '13 at 22:23

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.