Liberty, Ethics and Information / Liberté, Éthique et Information
An anonymous user wrote on March 25th, 2005 at 11:00 pm
Actually, a CFG can account for balanced parens. CFGs are recognized by nondeterministic pushdown automata. These have stacks. When encountering (, push something onto the stack. When encountering ), pop it.
Remember that a CFG is a grammar with rules of the form Symb -> Symb*. A CFG for an s-expr syntax consisting of only parens and symbols looks like this: Expr -> Atom | List List -> ( Expr List_end List_end -> ) | Expr List_end
I think you're probably thinking of linear grammars, which generate regular languages that are accepted by deterministic finite automata, which have no stack. Those cannot balance a possibly infinite number of parentheses, as their grammars must be finite.