1
$\begingroup$

I want to find a non-deterministic 2-tape Turing machine, that accepts the language L over $\Sigma=\{0,1\}$ in $n$ steps, with input of length $n$, $L=\{x1y \mid |y|=2|x|>0\}$.

Should the Turing machine do the following?

Each time that the machine reads 1 it should check if the length of the subword before 1 is equal to the half of the length of the subword after 1.

How can this be done by a non-deterministic 2-tape Turing machine? Could you give me a hint?

$$$$

EDIT:

The idea is the following:

We have to guess the position of $1$. In the state $z_1$ we copy the input of the first tape, till this $1$, to the second one. Then after having reached $1$, the head of the first tape will make $|x|$ to the right. If the input ends there, the input is accepted. If not, the input is rejected.

Is this correct?

Is the transition function then the following?

$(z_0, 1, \square)\mapsto (z_0,1,1,R,R) \mid (z_1, X,X,N,N)$

$(z_0, 0, \square)\mapsto (z_0,0,0,R,R)$

$(z_1, a, \square)\mapsto (z_1, a,a,R,R)$

$(z_1, X,X)\mapsto (z_2, a, \square, R, N)$

$(z_2, a, \square)\mapsto (z_2, a, \square, R, N)$

$(z_2,\square, \square )\mapsto (z_3, \square, \square, N, N)$

$\endgroup$
18
  • 1
    $\begingroup$ Please, explain what you mean by "accept the language" as it could mean several thing for a turing machine : reach a particular state, write a particular output on a specific tape, or just halt. $\endgroup$
    – Xoff
    Aug 15, 2016 at 13:47
  • 1
    $\begingroup$ What does it mean $L(M)$ ? $\endgroup$
    – Xoff
    Aug 15, 2016 at 13:56
  • 1
    $\begingroup$ So, this question is weird, because there is no need in a second tape, as being non deterministic, the machine doesn't need to write anything to reach an accepting state on $L$. $\endgroup$
    – Xoff
    Aug 15, 2016 at 14:13
  • 1
    $\begingroup$ Oops sorry, I read that $|y|=2$ and not $|y|=2|x|$, ok, you may need (but it's a convenience only) the second tape to verify that length of $y$ is twice the length of $x$. $\endgroup$
    – Xoff
    Aug 15, 2016 at 14:23
  • 2
    $\begingroup$ When you copy on tape 2, you go right on each tape. When you reach the guessed position, $y$ is on your right on tape 1, but the copy of $x$ is on your left on tape 2. To compare them, you need to go left on the tape 2 at some step, or you could never retrieve the copied information. $\endgroup$
    – Xoff
    Aug 15, 2016 at 14:38

2 Answers 2

Reset to default
1
$\begingroup$

Well since you have non-determinism, just copy the input to the second tape up to some guessed position (intended to be just before the "1"), and then check that the next symbol on the input tape is "1" and that the rest of the input is twice as long as what is on the second tape. Clearly any string in $L$ will be accepted for some sequence of guesses, and also any accepted string is in $L$. Just ensure that you handle the small cases correctly and don't accept "1".

It is (of course) also possible with a deterministic TM, but it uses $2n$ steps and is more troublesome. The easiest way is to read the first symbol of the input, and then read the rest in threes, each time appending one symbol to the second tape. After that, you know exactly where the "1" in the middle is supposed to be, and you can just read the input backwards from the end (where you last stopped) and check that the symbol at that location is really a "1".

$\endgroup$
6
  • $\begingroup$ How does then the transition function look like? How do we describe the guessed position? $\endgroup$
    – Mary Star
    Aug 13, 2016 at 22:46
  • $\begingroup$ @MaryStar: That's for you to figure out. To guess the position just means that at each step of my first sentence you non-deterministically either stop (guess it is there) or carry on. $\endgroup$
    – user21820
    Aug 14, 2016 at 1:45
  • $\begingroup$ But how can we formally define the guessed position? I got stuck right now... How can we know where we have to stop? $\endgroup$
    – Mary Star
    Aug 14, 2016 at 13:27
  • $\begingroup$ @MaryStar: I think you need to revise the definition of a non-deterministic TM. It is trivial to make it do what I've explained in my previous comment. $\endgroup$
    – user21820
    Aug 14, 2016 at 13:33
  • $\begingroup$ Could you take a look at the edit part of my question? Is the transition function correct? $\endgroup$
    – Mary Star
    Aug 14, 2016 at 21:18
0
$\begingroup$

Transitions are described with (Initial state, read (tape1), read (tape2)) -> (newState, write(tape1), write(tape2), move(tape1), move(tape2)).

I also suppose that the head is initially placed on the first (leftmost) letter of the input word (or blank if empty). Letters are 0,1 or B (blank).

The initial state is $I$, the acceptance state is $A$, the rejected state is $R$. The non deterministic machine accepts a word if it has at least one computation path that reach $A$.

  • $(I,0,B) \rightarrow (J,0,0,N,R)$
  • $(J,0,B) \rightarrow (I,0,0,R,R)$
  • $(I,1,B) \rightarrow (J,0,0,N,R) | (K,B,B,R,L)$
  • $(K,0|1,0) \rightarrow (K,0,0,R,L)$
  • $(K,B,B) \rightarrow (A,B,B,N,N)$

Any non defined transition goes to state $R$ (rejection).

The idea : First we use states $I$ and $J$ to write twice many 0 as we read 0 or 1 on tape 1. Then we compare the number of written 0 on tapes 2 with the number of 0 or 1 of the guessed $y$ with state $K$

$\endgroup$
2
  • $\begingroup$ And why does any defined transition go to state $R$ ? $\endgroup$
    – Mary Star
    Aug 15, 2016 at 15:54
  • $\begingroup$ "non defined" or should I wrote undefined ? @MaryStar $\endgroup$
    – Xoff
    Aug 16, 2016 at 6:37

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.