2018 November 7,
Carleton College, Joshua R. Davis
The space complexity class L consists of all problems that can be solved in logarithmic space. To make such a concept meaningful, we have to ignore the space used to store the input. For a precise definition of L, see Section 8.4 of our textbook. We will now do an enhanced version of Exercise 8.17.
A. Deciding whether a string of parentheses is a valid nest is one of our classic PDA problems. How much stack space did our PDA solution use?
B. Solve Exercise 8.17. (Hint: You need a different criterion for characterizing whether a string of parentheses is a valid nest.)