# Turing machine for balancing parentheses on a two letter alphabet

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

• Would $\mathtt{)()(}$ count as "balanced"? – user642796 Mar 26 '13 at 19:16
• I assume you're using $x$ to count the number of parenthesis of one type minus those of another. Perhaps try using ( for that as well? – Alex Becker Mar 26 '13 at 19:17
• Also, if $\Sigma$ supposed to be the input alphabet or the tape alphabet? – user642796 Mar 26 '13 at 19:23
• @ArthurFischer, thank you for your comment on balance. $)()($ should not be balanced. – Ronald Bernard Mar 26 '13 at 20:30
• @ArthurFischer, I made an edit concerning the alphabets. – Ronald Bernard Mar 26 '13 at 20:32

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.

• The Wikipedia definition I linked automatically includes a blank symbol $b$. – Ronald Bernard Mar 26 '13 at 20:27
• @Ronald: Then you can use that as the third symbol you need, can't you? – Henning Makholm Mar 26 '13 at 20:28
• Henning, first I apologize for the inaccuracy in the formulation of the question, I mixed up $\Gamma$ and $\Sigma$ and I want $\Gamma=\Sigma\cup\{b\}$ with $\Sigma=\{(,)\}$. On your second comment: If I use $b$ instead of $x$ my algorithms do not know when the end of the word is reached, e.g. $$\ldots b((()))bbb\ldots\to \ldots bb((b))bbb\ldots$$ then how does the algorithm if it should continue after the $b$ after $($? – Ronald Bernard Mar 26 '13 at 20:39
• @RonaldBernard: It can't; instead it's allowed to assume that the first $b$ marks the end of the input string. The definition of the machine recognizing a particular language $L$ is that when started on the tape $...bbb|wbbb...$ it will determine whether $w\in L$ or not. The definition doesn't say anything about what must happen if the initial tape has embedded blanks. – Henning Makholm Mar 26 '13 at 20:43
• Invert each mountaintop until nothing is left but hills $-$ I never thought of that. Nice. (Probably standard, but I don’t think that I’ve actually seen it before.) – Brian M. Scott Mar 26 '13 at 21:07

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.