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

  • $\begingroup$ Would $\mathtt{)()(}$ count as "balanced"? $\endgroup$ – user642796 Mar 26 '13 at 19:16
  • $\begingroup$ 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? $\endgroup$ – Alex Becker Mar 26 '13 at 19:17
  • $\begingroup$ Also, if $\Sigma$ supposed to be the input alphabet or the tape alphabet? $\endgroup$ – user642796 Mar 26 '13 at 19:23
  • $\begingroup$ @ArthurFischer, thank you for your comment on balance. $)()($ should not be balanced. $\endgroup$ – Ronald Bernard Mar 26 '13 at 20:30
  • $\begingroup$ @ArthurFischer, I made an edit concerning the alphabets. $\endgroup$ – 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.

  • $\begingroup$ The Wikipedia definition I linked automatically includes a blank symbol $b$. $\endgroup$ – Ronald Bernard Mar 26 '13 at 20:27
  • $\begingroup$ @Ronald: Then you can use that as the third symbol you need, can't you? $\endgroup$ – Henning Makholm Mar 26 '13 at 20:28
  • $\begingroup$ 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 $($? $\endgroup$ – Ronald Bernard Mar 26 '13 at 20:39
  • $\begingroup$ @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. $\endgroup$ – Henning Makholm Mar 26 '13 at 20:43
  • 1
    $\begingroup$ 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.) $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.