Overview

In the previous sections, we defined finite state automata, constructed them using the regular operations, and translated between FSAs and regular expressions. But given a particular FSA and string, how do we determine whether the machine accepts that string? And if it does, how do we recover the accepting path?

These questions separate three computational problems we can ask about a grammar \(G\):

1. Recognition: Is \(\boldsymbol\sigma \in \mathbb{L}(G)\)? A yes-or-no question.
2. Parsing: How does \(G\) accept \(\boldsymbol\sigma\)? This recovers the structural analysis—the path through an FSA, or (later) the parse tree for a CFG.
3. Generation: What strings does \(G\) produce? We already explored this in the section on generation, where we enumerated the strings in \(\mathbb{L}(G)\).

Recognition tests membership, parsing recovers an analysis, and generation enumerates strings. Every grammar formalism we encounter in this course—FSAs, CFGs, PCFGs, and the mildly context-sensitive formalisms—has its own algorithms for these problems. Their costs help us compare the formalisms. FSA recognition is linear in the input length, and a packed representation of accepting paths can be recovered with comparable graph-search machinery; explicitly listing all parses additionally costs at least the size of that output. Generation has no single input-length bound because an FSA may describe an infinite language: its cost depends on how much of the language is requested. For CFGs, general parsing takes \(O(n^3)\) time (CKY, Earley). For mildly context-sensitive grammars, the polynomial bound on parsing is one of the defining properties of the class.

The distinction between recognition and parsing matters because the parse carries structural information that recognition alone does not provide.