a deterministic context-free language

A deterministic context-free language is, simply, a language that some deterministic pushdown automaton recognises. Because a DPDA never guesses, these are the context-free languages that can be parsed by a single forward pass with no backtracking — the well-behaved, practically tractable corner of the context-free world. They form a proper subset of all context-free languages: every DCFL is context-free, but not every context-free language is a DCFL.

What makes a language land in this class is, intuitively, the absence of any unavoidable guess. The language a^n b^n is deterministic: a machine can tell exactly when to stop pushing and start popping, because the switch from a's to b's is right there in the input. By contrast, the language of even-length palindromes is context-free but NOT deterministic, because finding the midpoint requires a guess no deterministic machine can make. Another telling example: the language {a^n b^n} union {a^n b^2n} is context-free but not deterministic — a deterministic machine cannot commit, after seeing the a's, to which of the two patterns to expect.

This class is the theoretical foundation of practical parsing. The grammars used for programming languages — LL grammars and especially LR grammars — generate exactly languages a deterministic pushdown machine can handle, which is why a compiler can parse source code in linear time with a single left-to-right scan and no backtracking. The deterministic context-free languages also enjoy nicer closure properties than general CFLs: notably they ARE closed under complement, unlike the full context-free class. The honest caveat is that this niceness comes at the price of expressiveness: some perfectly reasonable context-free languages simply lie outside it.