2. Space Complexity (6 points)

Let A be the language of properly nested parentheses. For example, (()) and (()(()))() are in A, but )( is not.

Show that A is in L (i.e., show you can decide whether a sequence of n paren- theses are properly nested using only log(n) space).

Hint: Use your space to track the number of left parentheses versus right parentheses seen so far.