I am having trouble giving the description of a Turing machine that goes for $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$. What I have so far is:

If we start with a blank, the string is empty and it should accept, if not, start reading $0$s and I thought marking the $0$s with $X$ and the $1$s with $Y$ would be OK. After we reach a $1$, start marking $0$. Now comes the part I'm worried about, what do I do when the 2nd round of $0$s comes? How will I check if there are equal amounts of $0$s and $1$s?

Thanks in advance

  • $\begingroup$ If you're having trouble counting with a regular TM, you might consider solving the problem with a multi-tape TM (one tape for the input string, another to write the first half of the input string), or even a two-stack PDA (equivalent to a TM in power) which probably would be simpler in this case. I don't know if this would be an acceptable answer, in your case. But it's a start. $\endgroup$ May 23 '14 at 12:36
  • $\begingroup$ We've not yet gone over multi-tape TMs, so i don't think it is what's looked for. But i'll look it up, maybe i can use it anyway. Thanks $\endgroup$
    – DakkVader
    May 23 '14 at 12:42

What I tend to do when it comes to counting with a tape is to go back and forth on the tape, marking the relevant portions of the tape as I'm reading new input.

To recognize the language $0^n1^n$ with a Turing machine (not that you'd need the power of a Turing machine, but for illustrative purposes), you can read the first $n$ $0$s, and then when you read the first $1$, mark that $1$ (write $1'$ in that cell), then go back all the way to the first $0$ and mark that, too (writing $0'$). Then go back to the next $1$ (the one to the right of the cell with the $1'$) and write $1'$, go back to the next $0$ that is not marked, and mark that. When you run out of $1$s to read/mark, you have to go back and make sure that all $0$s have been marked. If this is the case, accept the language. If not, or if any other deviation has occurred during the operation of the machine (e.g. encountered some input symbol other than a $0$ or a $1$, read and marked a $1$ but there were no $0$s left to mark; these are treated like undefined transitions), you must reject the language.

Say you are given the string $0000111$ as input.
After counting two $1$s:

$0' 0' 0 \,0 \,1' 1' 1\,$

After counting three $1$s:

$0' 0' 0'0 \,1' 1' 1'$

Now there is one $0$ left that is not marked; reject the language.

For your language, it is simple (but, like the above, pretty tedious) to use this strategy to recognize the language. The variation comes in keeping track of what parts of the previous input to mark, and how to get back to the next input cell to read.

Aside: This can be generalized to multiplication, for example to recognizing the language $0^n1^m0^{n \cdot m}$.

  • $\begingroup$ Can i move the tape head more then 1 cell at a time? Wouldn't this give me an enourmus table for the function? $\endgroup$
    – DakkVader
    May 23 '14 at 13:26
  • $\begingroup$ @user3125297 In order to move back and forth; you can have states for moving left and right on the tape, when you want to find the next unmarked $0$ and the next input $1$, respectively. You will need transitions for dealing with these traversals, but there shouldn't be a need for a lot of them; you just need to make sure to keep heading in the right direction, only stopping when you find a marked $0$ or $1$ (depending on if you're going left or right). $\endgroup$ May 23 '14 at 13:36
  • $\begingroup$ I'll look into it , thanks alot! I'll get back to you later today / tomorrow with how it went. Thanks. $\endgroup$
    – DakkVader
    May 23 '14 at 13:40

Turning Machine compares such numbers by zig-zaging across the tape. It can mark first 0 from first $0^n$ and go to all the way across 1s to mark first 0 from second $0^n$, then return back to first $0 ^n$ to mark second 0 and so on.

And yes, you don't need extra tape alphabet Y. X can do fine for 1s too without conflicting with 0s.

The transition functions defining zig-zaging aren't that complex. They're like loops with loop break rules.


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.