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!