# Tricky Turing Machine state diagram

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?

• Given the string $11113$, it could be $a=3, b=1$ or $a=2, b=2$. You, however, don't need to know $a, b$ to know that $11113 \in A$. Commented Mar 21, 2014 at 19:54

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.

• hey, thank you! what would the transitions be if a=c instead of a >= b? how would you create a TM for that? Commented Mar 22, 2014 at 4:53

This is a context free language given by \begin{align} S &\to S2 | S3 | T \\ T &\to 0T | 1T | 0T1 | 0T2 | 1T1 | 1T2 | \varepsilon \end{align}

I'm not suggesting that you should write down a TM that parses CF languages, although you could. I'm suggesting that you should take into account the properties of a language, not the properties of one of its descriptions, when writing a TM for it.

• I don't see how the grammar would help me figure out the transition between states in the TM. can you show me an example? or a solution? Commented Mar 21, 2014 at 20:38