[Solved]: Having trouble with turing machine over language $L = \{0^n 1^m 0^n 1^m \mid m,n \geq 0\}$

Problem Detail: 

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

Asked By : DakkVader

Answered By : Guildenstern

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.

Example
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}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/26015

3.2K people like this

 Download Related Notes/Documents