If you want to make money online : Register now

# [Solved]: Tricky Turing Machine state diagram

, ,
Problem Detail:

what would the Turing machine state diagram be for this language: $A=\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\}$ ?

how would the turing machine design know the size of $(1 \cup 2)^b$ ? since this contains elements from the first and last parts, would it be impossible to determine?

#### Answered By : Kaya

As a supplement to the excellent recommendation by Karolis Juodelé I present some informal 'pseudocode' for how to run a TM to accept $L=\{ (0 \cup 1)^a(1 \cup 2)^b(2\cup 3)^c \mid a \geq b\}$. The key observation is that we may let $b=0$ and ignore the condition $a\geq b$ in all cases but those words $w$ which contain the subword $21$. In the situation where $21\in w$ the borders for when the $b$ count starts and ends are at the first occurrence of $2$ and the last occurrence of $1$ respectively.

Initial tape reads $\underline\Delta w\Delta^\star$, step right and replace all $0,1$ with $A$. When a $2$ is read overwrite it with a $B$ and proceed right overwriting $2$s with $B$s until either a $1$ or $3$ is encountered. If a $3$ is encountered then we know either $b=0$ or $w\not\in L$ so we finish by accepting iff the remainder of the string contains only the symbols $2,3$

If we encounter a $1$ we are in the case where $b\neq0$ and we need to enforce the $a\geq b$ requirement (also replace it with a $C$). Continue right replacing the symbols $1$ with $C$ and $2$ with $B$ until a $3$ is encountered or the string terminates. If a $3$ is encountered read the rest of the string to make sure it is only the symbols $3,2$ until the end (and replace them with $\Delta$s). Once the end of the string is reached step backwards (left) replacing any $B$ encountered with a $\Delta$ until the tape head rests on a $C$. Then ensure that $\#(A)\geq\#(B)+\#(C)$ and if this is satisfied accept, otherwise reject.

###### Best Answer from StackOverflow

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

3.2K people like this