Context-Free Grammars

Math for CS · Axiom Academy

The formal language model behind every programming language syntax Regular expressions are powerful, but they have a hard limit. They cannot count. Imagine you want to describe the language of balanced parentheses : strings like () , (()) , (()()) . Every opening parenthesis must eventually be closed. This sounds simple, but no finite automaton (and no regex) can recognize this language. The reason: a DFA only has finitely many states, but balanced parentheses can nest arbitrarily deep, so the machine would need infinite memory to remember "how deep am I right now?" We need a more powerful description tool — something that captures recursive, nested structure. That tool is the context-free grammar (CFG), and it powers the parsers inside every compiler, every JSON loader, and every HTML renderer. A context-free grammar is a 4-tuple. Each piece has a job. V is a finite set of variables (also called nonterminals). These are placeholders that get rewritten. is a finite set of terminals — the actual alphabet of the language. We require . R is a finite set of production rules . Each rule has the form where and . The phrase "context-free" refers to the left-hand side of every rule: it must be a single variable, with no surrounding context. The grammar can rewrite A no matter what appears around it. Compare this to context-sensitive grammars, where rules can mention neighbors.

This is the written version of the interactive lesson above. See the full Math for CS course.