If I have a language over alphabet $\Sigma=\{(,[,],)\}$. How can I find out if a tape has a valid (matching) parentheses structure in linear time?

So far, my attempt is as follows:

  • state 0: accept ( or [ i.e. no open parentheses
  • state 1: accept ), ( or [ i.e. a ( has occurred previously
  • state 2: accept ], ( or [ i.e. a [ has occurred previously

The problem with this setup is that I won't know how many ( or [ has occurred previously. One idea was to store how many occurrences of open parentheses of each kind on the second tape, but this would potentially require an infinite tape alphabet. So it seems as if I'm approaching the problem the wrong way.

How can I create a Turing machine that wouldn't need to store the amount of open parentheses while still being able to accomplish this in linear time?

I looked at this question already, but couldn't figure out how this would be applicable to multiple types of parentheses and still be done in linear time.

Any input would be much appreciated!

  • $\begingroup$ Your attempt so far appears to be a DFA, which can't work, since the language isn't regular. Note also that this question is about having two tapes, whereas the one you link to is about two states, so probably won't help. You can store numbers on the second tape in binary: you don't need an infinite alphabet. $\endgroup$ – David Richerby Jul 4 '17 at 15:35

As others have pointed out, you can use a stack to check for matching parentheses. Such manipulation is the base idea of the shunting yard algorithm by Dijkstra.


Hint: use the second tape to store the stack of open brackets and parentheses you've seen. Each time you see a close, manipulate the stack appropriately.

  • $\begingroup$ Thanks for the input! Could you elaborate a bit more on the functionality of the stack? $\endgroup$ – Void Jul 4 '17 at 16:46
  • $\begingroup$ I'm not sure I can really say more without solving the exercise for you. I've told you what should go on the stack (each time you see a ( or a [, you put it on the stack) so you just need to figure out what to do when you see ) or ]. $\endgroup$ – David Richerby Jul 4 '17 at 17:00
  • $\begingroup$ Ok, maybe I'm seeing this the wrong way, but isn't the time complexity surpass linear time by having to move the second head back and forth like that? $\endgroup$ – Void Jul 4 '17 at 17:11
  • $\begingroup$ The point of using a stack is that the second head never has to move more than one step to find the thing it needs. $\endgroup$ – David Richerby Jul 4 '17 at 17:13
  • $\begingroup$ @Void each symbol the main head reads only results in at most 2 total moves of the heads (one to move the main head forward and maybe one to optionally move the second head 1 space when pushing or popping) $\endgroup$ – ratchet freak Jul 5 '17 at 11:09

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.