We want to give a logspace algorithm for deciding the set of strings of properly nested parenthesis and brackets. Consider the following two-stage logspace algorithm: Stage 1: Using two counters, make a pass through the input from left to right. Each time a ( is encountered, increase P by 1; each time a ) is encountered, decrease P by 1. Same for B and [ and ]. So P and B are the counters for parenthesis and brackets, respectively. Notice that |P| and |B| are bounded by log(|w|) where w in {(,),[,]}^* is the input. If at any time P or B <0, or by the end P and B are not 0, then the parenthesis and brackets are not properly paired. Note that stage 1 could also have been broken up into two sub-stages, where we first count P and then count B; we don't have to count them simultaneously. Stage 2: In the second stage we want to check that the parenthesis and brackets are closed in the right order. For example, ([)] has the right count after stage 1, but it is not a properly nested string. We maintain 4 pointers to the input (so each has length at most log(|w|)). We have pointers Pl,Pr,Bl,Br, standing for left parenthesis, right parenthesis, left bracket, and right bracket, respectively. We process the input from left to right, as follows: at each step, either Pl or Bl points to ( or [. Then, Pr or Br searches for the corresponding ) or ] starting at the left ( or [. The search can be implemented with a single counter C which increases by 1 on left parenthesis (bracket) and decreases by 1 on right parenthesis (bracket). If stage 1 was successful, we know such a right parenthesis (bracket) can be found. So now Pr or Br points to the right ) or ]. Suppose that the next symbol to the right of ( is also (. Then the process is repeated. Similarly, if the next symbol to the right of [ is [, the process is repeated. Closing parenthesis/brackets are ignored. However, if there is alternation---the next symbol to the right of ( is [---then we have to check that BrPr, and so it is not a proper string. Consider: ([][()]) At first Pl=1 and Pr=8. Then Bl=2 and Br=3