# How to calculate whether a parenthesis string is valid using a 2-tape Turing machine?

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!

• 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. – David Richerby Jul 4 '17 at 15:35

• 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 ]. – David Richerby Jul 4 '17 at 17:00