Turing machine for balancing parentheses on a two letter alphabet

Question

How to construct a Turing machine $M=(Q,\Gamma,b,\Sigma,\delta,q_0,F)$ which decides if a sting on the alphabet $\{(,)\}$ is ''balanced'' (e.g. $(()())$ is balanced and $))(($ or $()(($ is not) with alphabet $\Sigma=\{(,)\}$ and $\Gamma=\Sigma\cup\{b\}$?

In all my attempts, I needed an alphabet containing at least one more letter, e.g. $\Gamma=\{(,),x,b\}$.

Answer 1

You need an additional symbol besides ( and ) to encode the end of the input string anyway.

I think I've seen formalizations of Turing machines that don't allow the machine to write this blank symbol, which makes things trickier -- but not essentially so; one can create a machine that starts by expanding the input string to double length without ever needing to write a symbol not in the working alphabet.

But such a general construction isn't actually necessary in this case -- you can keep scanning the string from left to right and rewrite any instance of (() to ()( until there are no more (() left. If the resulting configuration is a sequence of (), then the original string was balanced, otherwise not.

Answer 2

First copy the input string, inserting blanks; e.g., the input string ())( turns progressively into ))(b(, )(b(b), (b(b)b), and b(b)b)b(. Now bb signals the ends of the useful string, b( is a left parenthesis, b) is a right parenthesis, and you can use any of the four double parenthesis combinations as extra symbols. You have to be a bit careful with your coding to keep the parities of the cells straight, but in effect you’re using even-odd pairs of adjacent cells, each containing one of three symbols, as if they were single cells each containing one of nine symbols.