A Brutal Look at Balanced Parentheses, Computing Machines, and Pushdown Automata

Summary

As discussed in Pattern Matching and Recursion, a well-known programming puzzle is to write a function that determines whether a string of parentheses is “balanced,” i.e. each opening parenthesis has a corresponding closing parenthesis, and the parentheses are properly nested. For example: Input Output '' true the empty string is balanced '()' true '(())' true parentheses can nest '()()' true multiple pairs are acceptable '(()()())()' true multiple pairs can nest '((()' false missing closing parentheses '()))' false missing opening parentheses ')(' false close before open This problem is amenable to all sorts of solutions, from the pedestrian to the fanciful. But it is also an entry point to exploring some of fundamental questions around computability. This problem is part of a class of problems that all have the same basic form: We have a language, by which we mean, we have a set of strings. Each string must be finite in length, although the set itself may have infinitely many members. We wish to construct a program that can “recognize” (sometimes called “accept”) strings that are members of the language, while rejecting strings that are not. The “recognizer” is constrained to consume the symbols of each string one at a time. Computer scientists study this problem by asking themselves, “Given a particular language, what is the simplest possible machine that can recognize that language?” We’ll do the same thing. Instead of asking ourselves, “What’s the wildest, weirdest program for recognizing balanced parentheses,” we’ll ask, “What’s the simplest possible computing machine that can recognize balanced parentheses?” That will lead us on an exploration of formal languages, from regular languages, to deterministic context-free languages, and finally to context-free languages. And as we go, we’ll look at fundamental computing machines, from deterministic finite automata, to deterministic pushdown automata, and finally to pushdown automata. prelude: why is this a “bruta...