Context-Free Grammars — Mathematics Knowledge System

Overview

A context-free grammar (CFG) is a set of rewriting rules that generates strings by repeatedly replacing symbols, powerful enough to describe nested structures — balanced parentheses, arithmetic expressions, and the syntax of every programming language — that regular expressions cannot capture. CFGs sit one level above regular languages in the Chomsky hierarchy of formal languages.

Intuition

A regular expression can't 'count' — it can't ensure a string has as many closing parens as opening ones, because that requires unbounded memory. A CFG can, because its rules can recursively nest: 'an expression is either a number, or (an expression)' directly encodes arbitrary nesting depth. This is exactly why programming language syntax is specified by grammars, not regular expressions.

Formal Definition

Definition

A context-free grammar is a 4-tuple:

G = (V, \Sigma, R, S)

Definition

A \to \alpha, \quad A \in V, \ \alpha \in (V \cup \Sigma)^*

Each rule replaces a single nonterminal A with a string α of terminals/nonterminals

Notation

Notation	Meaning
$V$	The set of nonterminal symbols
$\Sigma$	The set of terminal symbols (the alphabet)
$R$	The set of production rules
$S$	The start symbol

Derivation

A grammar for balanced parentheses, showing it generates '(())' via successive rule applications:

S \to (S)S \mid \varepsilon

S \Rightarrow (S)S \Rightarrow ((S)S)S \Rightarrow ((\varepsilon)\varepsilon)\varepsilon = (())

Properties

Chomsky hierarchy position

\text{Regular languages} \subsetneq \text{Context-free languages} \subsetneq \text{Context-sensitive languages}

Pushdown automata equivalence

\text{A language is context-free} \iff \text{it is recognized by some pushdown automaton (finite automaton + a stack)}

Applications

Real-world · Computer Science

Every programming language's syntax (if-statements, expressions, nested blocks) is specified by a CFG, parsed by a compiler's parser.

Worked Examples

1
Each rule application adds one a on the left and one b on the right.
$S \to aSb \mid \varepsilon$

✓ Answer

S → aSb | ε

Practice Problems

Mediumfree response

Show that aⁿbⁿ (n≥0) cannot be described by a regular expression (intuitively).

Mediumapplication

Programming languages and data formats like JSON are defined by context-free grammars, not regular expressions. Why is a CFG necessary to parse JSON?

Mediumapplication

When a compiler reads '3 + 4 * 5', what structure does its parser build from the language's context-free grammar, and how does the grammar enforce that multiplication binds tighter than addition?

MediumMultiple choice

The 'dangling else' problem (which 'if' does an 'else' attach to?) is an example of:

A regular languageAn ambiguous context-free grammar (a string with more than one parse tree)An undecidable problemA syntax error

Common Mistakes

Common Mistake

Assuming every context-free grammar is unambiguous.

Many CFGs are ambiguous (a string has multiple valid parse trees), which is a real problem in language design — e.g. the classic 'dangling else' ambiguity in C-like languages.

Quiz

Summary

A CFG generates strings via rewriting rules A → α on nonterminals.
CFGs can express nested/recursive structure that regular expressions cannot.
Context-free languages are exactly those recognized by pushdown automata (finite automaton + stack).
Programming language syntax is universally specified using context-free grammars.

References

WebsiteWikipedia — Context-free grammar