Context-Free Grammars
Recursive language descriptions, derivations, ambiguity, and correctness
Moving beyond finite state
Finite automata recognize the regular languages, but many natural computational patterns are not regular:
- matched quantities, such as \(\{a^nb^n:n\ge0\}\);
- balanced delimiters;
- nested expressions; and
- palindromes.
These languages require a form of memory that can grow with the input. Our next language-description model is the context-free grammar (CFG), and the corresponding machine model will be the pushdown automaton (PDA), which adds a stack to finite-state control.
Why build abstract models?
The history of automata theory connects attempts to model calculation, language, and even aspects of human cognition.
Alan Turing’s machines modeled the essential steps performed by human “computers.” McCulloch and Pitts modeled simplified neural activity, and Stephen Kleene studied how finite automata could represent events in neural networks.
Kleene emphasized a general scientific strategy: when reality is too complicated to understand all at once, isolate a manageable domain, construct an approximate model, and then understand that model thoroughly.
The goal is not to claim that the abstraction captures every detail. It is to identify which conclusions follow from its assumptions.
Modeling language
Noam Chomsky developed mathematical models of grammar that profoundly influenced linguistics and computer science.
A generative grammar describes how larger structures can be produced by repeatedly applying replacement rules:
\[ \text{pattern}\rightarrow\text{replacement}. \]
For example, a simplified grammar might contain rules such as
\[ S\rightarrow NP\ VP, \]
\[ NP\rightarrow Adj\ N, \]
\[ VP\rightarrow V\ Adv. \]
Lexical rules then replace grammatical categories with words:
\[ Adj\rightarrow\texttt{colorless}\mid\texttt{green}, \]
\[ N\rightarrow\texttt{ideas},\qquad V\rightarrow\texttt{sleep},\qquad Adv\rightarrow\texttt{furiously}. \]
One possible derivation yields Chomsky’s famous syntactically well-formed but semantically peculiar sentence:
Colorless green ideas sleep furiously.
The example separates form from meaning: a grammar can characterize structural well-formedness without deciding whether a sentence is sensible.
Recursion creates unbounded structure
Compare these noun-phrase rules:
\[ NP\rightarrow Adj\ N \]
and
\[ NP\rightarrow Adj\ NP\mid N. \]
The first permits one adjective. The recursive second rule permits arbitrarily many adjectives because \(NP\) can contain another \(NP\).
Recursion is the source of a grammar’s ability to generate infinitely many structures from finitely many rules. Similar recursive organization appears in nested program blocks, arithmetic expressions, lists, trees, and function calls.
Language, cognition, and computation
The role of recursion in human language has motivated debate about which linguistic abilities are uniquely human and how they might have evolved. Research involving Kanzi and Sue Savage-Rumbaugh explored symbol learning and combinatorial communication in bonobos.
These questions provide historical motivation, but our mathematical objective is narrower: understand what different formal grammar systems can generate.
Recognizers and generators
Machines and grammars provide two complementary views of language.
Machine view
A string belongs to a language when a machine accepts it. The power of a machine model is described by the languages its machines can recognize.
Grammar view
A string belongs to a language when a grammar can generate it. The power of a grammar model is described by the languages its grammars can generate.
For regular languages, finite automata are recognizers and regular expressions are textual descriptions. For context-free languages, pushdown automata are recognizers and context-free grammars are generators.
| Language class | Recognizing machine | Textual or generative representation |
|---|---|---|
| Regular | Finite automaton | Regular expression |
| Context-free | Pushdown automaton | Context-free grammar |
Context-free grammars as recursive definitions
A CFG is a compact way to write a recursive definition of a language.
When designing a grammar, ask:
- Base case: What are the shortest strings in the language?
- Recursive case: How can a smaller valid string be expanded into a larger valid string?
Example: \(101^*\)
The shortest string is 10. Longer strings are formed by appending 1s:
\[ S\rightarrow10\mid S1. \]
Example: \((00)^*10\)
The shortest string is 10. Longer strings are formed by adding 00 to the front:
\[ S\rightarrow10\mid00S. \]
Example: \(01^*0(10)^*\)
Break the language into two concatenated pieces:
\[ S\rightarrow AB, \]
\[ A\rightarrow0\mid A1, \]
\[ B\rightarrow0\mid B10. \]
Variable \(A\) generates \(01^*\), while \(B\) generates \(0(10)^*\).
Example: \((10^*1)^*\)
One grammar is
\[ S\rightarrow\varepsilon\mid SAB, \]
\[ A\rightarrow1\mid A0, \]
\[ B\rightarrow1. \]
Each \(AB\) contributes one block from \(10^*1\), and the \(S\) rule permits any number of blocks.
Palindromes
Over \(\Sigma=\{a,b\}\), palindromes have the recursive definition:
- \(\varepsilon\), \(a\), and \(b\) are palindromes;
- if \(w\) is a palindrome, then \(awa\) and \(bwb\) are palindromes; and
- no other strings are palindromes.
The corresponding grammar is
\[ S\rightarrow\varepsilon\mid a\mid b\mid aSa\mid bSb. \]
This captures both even- and odd-length palindromes. The recursive variable remembers the need to match the symbol placed at the beginning with the symbol placed at the end.
Equal numbers in sequence
The classic nonregular language
\[ \{a^nb^n:n\ge0\} \]
has the simple CFG
\[ S\rightarrow\varepsilon\mid aSb. \]
Each recursive step adds one a and one b, preserving equality while maintaining the required order.
Formal definition of a CFG
A context-free grammar is a four-tuple
\[ G=(V,\Sigma,R,S), \]
where:
- \(V\) is a finite set of variables, or nonterminal symbols;
- \(\Sigma\) is a finite set of terminal symbols, with \(V\cap\Sigma=\varnothing\);
- \(R\) is a finite set of production rules; and
- \(S\in V\) is the start variable.
Each production has the form
\[ A\rightarrow\alpha, \]
where \(A\in V\) and \(\alpha\in(V\cup\Sigma)^*\).
The empty string \(\varepsilon\) is not a terminal symbol. It denotes an empty right-hand side and may be produced by a rule such as \(A\rightarrow\varepsilon\).
Several productions with the same left side are commonly combined using a vertical bar:
\[ A\rightarrow\alpha_1\mid\alpha_2\mid\cdots\mid\alpha_k. \]
The grammar is called context-free because the variable \(A\) may be replaced regardless of the symbols surrounding it.
Context-free languages
A language is context-free if some CFG generates it.
CFGs can generate every regular language and some nonregular languages. For comparison:
\[ 0^*1^* \]
can be generated by
\[ S\rightarrow AB,qquad A\rightarrow\varepsilon\mid A0,qquad B\rightarrow\varepsilon\mid B1, \]
whereas
\[ \{0^n1^n:n\ge0\} \]
can be generated by
\[ S\rightarrow\varepsilon\mid0S1. \]
Thus the regular languages form a proper subset of the context-free languages:
\[ \mathrm{REG}\subsetneq\mathrm{CFL}. \]
Why context-free grammars matter
CFGs were motivated partly by natural-language structure, but they became central to programming languages. They describe constructs such as:
- nested parentheses and braces;
- arithmetic expressions;
- conditional statements;
- blocks and scopes; and
- recursive syntactic structures.
Natural languages often require contextual and semantic constraints that CFGs alone do not capture. For programming-language syntax, however, CFGs are exceptionally useful.
Our two main design questions are:
- Given a grammar, which strings can it generate?
- Given a language, can we construct a grammar that generates exactly it?
Deriving strings
A derivation is a sequence of rule applications beginning with the start variable and ending with a string of terminals.
Consider
\[ S\rightarrow AB, \]
\[ A\rightarrow\varepsilon\mid1A, \]
\[ B\rightarrow\varepsilon\mid1B0. \]
Variable \(A\) generates \(1^i\), while \(B\) generates \(1^j0^j\). Therefore,
\[ L(G)=\{1^{i+j}0^j:i,j\ge0\} = \{1^m0^n:m\ge n\ge0\}. \]
A leftmost derivation of 1110 is
\[ S\Rightarrow AB \Rightarrow1AB \Rightarrow11AB \Rightarrow11B \Rightarrow111B0 \Rightarrow1110. \]
At each step, the leftmost remaining variable is replaced.
Parse trees and derivation order
A parse tree records the hierarchical structure of a derivation:
- the root is the start variable;
- internal nodes are variables;
- children show the right side of the production used; and
- leaves, read from left to right, form the derived string.
Different rule-application orders may describe the same parse tree.
- In a leftmost derivation, replace the leftmost variable at each step.
- In a rightmost derivation, replace the rightmost variable at each step.
The structural parse tree—not the incidental order in which independent replacements are performed—determines the interpretation.
More grammar-reading examples
Recursive insertion
Consider
\[ S\rightarrow0\mid001S\mid S001\mid S11. \]
Every derivation begins with 0 and repeatedly adds one of the listed substrings to the left or right. To characterize the language precisely, identify an invariant preserved by every rule and then determine whether that invariant is sufficient.
Arithmetic expressions
The grammar
\[ S\rightarrow S+S\mid S-S\mid S*S\mid S/S\mid(S)\mid a \]
generates arithmetic expressions over the identifier a. It does not specify conventional precedence or associativity, which makes it ambiguous.
Designing CFGs
Useful strategies include:
- translate a recursive definition directly;
- divide the language into simpler pieces;
- use closure under union, concatenation, and star;
- check whether the language is regular and convert a regular representation;
- identify substrings whose quantities must be linked; and
- use a rule of the form \(R\rightarrow uRv\) to add related material on both sides.
For example,
\[ R\rightarrow\varepsilon\mid0R1 \]
links one 0 with one later 1.
Design exercises
Construct CFGs for:
- \(0^*11^*0(0\cup1)^*\);
- \((000)^*11\);
- \(1^*0(1\cup01^*0)^*\);
- \((a\cup ba)b^*a\);
- \(\{0^n1^n:n\ge0\}\);
- \(\{0^i1^j:i>j\}\);
- \(\{a^ib^jc^k:i=j+k\}\);
- \(\{0^i1^j0^k:j>i+k\}\); and
- balanced braces.
For linked counts, decide which symbols should be introduced by the same recursive production.
Closure properties of CFLs
Theorem. If \(L_1\) and \(L_2\) are context-free, then so are
\[L_1\cup L_2,\qquad L_1L_2,\qquad L_1^*.\]
Suppose grammars \(G_1\) and \(G_2\) have distinct variables and start variables \(S_1\) and \(S_2\).
Union
Add a new start variable \(S\) and the rule
\[ S\rightarrow S_1\mid S_2. \]
Concatenation
Add a new start variable with
\[ S\rightarrow S_1S_2. \]
Kleene star
Add a new start variable with
\[ S\rightarrow\varepsilon\mid SS_1. \]
Because regular expressions are built from individual symbols, \(\varepsilon\), \(\varnothing\), union, concatenation, and star, these constructions also prove that every regular language is context-free.
CFLs are not closed under everything
Let
\[ L_1=\{1^i2^i3^j:i,j\ge0\} \]
and
\[ L_2=\{1^i2^j3^j:i,j\ge0\}. \]
Both languages are context-free, but
\[ L_1\cap L_2=\{1^n2^n3^n:n\ge0\}, \]
which is not context-free. Therefore, CFLs are not closed under intersection.
If CFLs were closed under complement, De Morgan’s law
\[ A\cap B=\overline{\overline{A}\cup\overline{B}} \]
would imply closure under intersection. Because they are not closed under intersection, CFLs cannot be closed under complement either.
This is an important contrast with regular languages.
Ambiguous grammars
A grammar is ambiguous if some string in its language has two distinct parse trees. Equivalently, the string has two distinct leftmost derivations.
Consider
\[ S\rightarrow S+S\mid S*S\mid(S)\mid a. \]
The string
a+a*acan be parsed as either
\[ a+(a*a) \]
or
\[ (a+a)*a. \]
The grammar therefore fails to encode multiplication precedence.
Other ambiguity exercises include:
\[ S\rightarrow SS\mid\{S\}\mid\varepsilon, \]
\[ S\rightarrow SS\mid a\mid b, \]
and
\[ S\rightarrow ABA,qquad A\rightarrow aA\mid\varepsilon,qquad B\rightarrow bB\mid\varepsilon. \]
To prove ambiguity, exhibit one string and two distinct parse trees or leftmost derivations.
Removing ambiguity
Ambiguity is usually a property of a grammar rather than its language. A language may have both ambiguous and unambiguous grammars. Some context-free languages, however, are inherently ambiguous: every CFG generating them is ambiguous.
For balanced braces, an unambiguous grammar is
\[ S\rightarrow\{S\}S\mid\varepsilon. \]
The first pair of matching braces and the remainder of the string are uniquely separated.
For arithmetic expressions, encode precedence with separate variables:
\[ E\rightarrow E+T\mid T, \]
\[ T\rightarrow T*F\mid F, \]
\[ F\rightarrow(E)\mid a. \]
Here multiplication is nested more deeply than addition, so it binds more tightly. The left recursion makes both operators left-associative.
Unambiguous grammars matter because compilers need a unique structural interpretation of a program.
Chomsky normal form
A CFG is in Chomsky normal form (CNF) when every production has one of these forms:
\[ A\rightarrow BC \]
or
\[ A\rightarrow a, \]
where \(A,B,C\) are variables and \(a\) is a terminal. The special rule \(S\rightarrow\varepsilon\) may be allowed when \(\varepsilon\) belongs to the language, provided the start variable does not appear on a right-hand side.
Theorem. Every context-free language is generated by some CFG in Chomsky normal form.
The standard conversion removes or replaces:
- epsilon productions;
- unit productions such as \(A\rightarrow B\);
- useless variables;
- terminals mixed into long right-hand sides; and
- right-hand sides containing more than two variables.
Why normal form is useful
A CNF derivation of a nonempty string of length \(k\) has a binary parse tree with:
- \(k\) leaves corresponding to terminal productions; and
- \(k-1\) internal branching productions.
Thus it uses exactly \(2k-1\) production steps.
This bounded structure supports algorithms for the membership problem:
Given a CFG \(G\) and a string \(w\), is \(w\in L(G)\)?
The CYK algorithm, for example, uses CNF to solve membership with dynamic programming. This is an early example of connecting a formal model with questions of decidability and algorithmic complexity.
Proving that a grammar is correct
Given a proposed grammar \(G\) for a target language \(L\), examples are not enough. We must prove set equality:
\[ L=L(G). \]
This requires both inclusions.
Completeness: \(L\subseteq L(G)\)
Every intended string can be generated by the grammar. A proof usually uses induction to explain how to derive arbitrary strings in \(L\).
Soundness: \(L(G)\subseteq L\)
Every string generated by the grammar has the required property. A proof usually uses induction on the derivation or parse tree and considers every possible production.
The two directions answer different questions:
- Does the grammar generate enough strings?
- Does the grammar generate only correct strings?
Correctness example: \(\{0^n1^n:n\ge0\}\)
Let
\[ G:S\rightarrow\varepsilon\mid0S1 \]
and
\[ L=\{0^n1^n:n\ge0\}. \]
Prove \(L\subseteq L(G)\)
We use induction on \(n\).
Base case: For \(n=0\), \(0^01^0=\varepsilon\), and \(S\Rightarrow\varepsilon\).
Inductive hypothesis: Assume \(S\Rightarrow^*0^n1^n\).
Inductive step: Then
\[ S\Rightarrow0S1\Rightarrow^*0(0^n1^n)1=0^{n+1}1^{n+1}. \]
Therefore, every string in \(L\) is generated by \(G\).
Prove \(L(G)\subseteq L\)
Use induction on the number of recursive applications of \(S\rightarrow0S1\).
- Applying it zero times and then using \(S\rightarrow\varepsilon\) produces \(\varepsilon=0^01^0\).
- If \(n\) applications produce \(0^n1^n\), one additional application produces \(0^{n+1}1^{n+1}\).
No other productions exist, so every generated string belongs to \(L\). Hence
\[ L(G)=\{0^n1^n:n\ge0\}. \]
Correctness example: an even number of zeros
Consider
\[ G:S\rightarrow\varepsilon\mid S1\mid S0S0. \]
We claim that \(G\) generates exactly the binary strings containing an even number of 0s.
Soundness
Proceed by induction on the parse tree.
\(S\rightarrow\varepsilon\) contributes zero
0s.If \(S\Rightarrow^*w\) has an even number of
0s, then \(S1\Rightarrow^*w1\) has the same number.If two occurrences of \(S\) derive \(u\) and \(v\), each with an even number of
0s, then\[ S0S0\Rightarrow^*u0v0 \]
has an even number from \(u\), an even number from \(v\), and two additional
0s.
Thus every generated string has an even number of 0s.
Completeness
For the reverse inclusion, induct on string length and consider how a target string can be decomposed:
- a final
1can be produced with \(S\rightarrow S1\); - when the string contains
0s, select two0s that divide it into portions with even-zero structure and use \(S\rightarrow S0S0\); and - the empty string uses \(S\rightarrow\varepsilon\).
This direction requires more care because we must show that every arrangement of an even number of 0s admits a decomposition matching one of the productions.
Example derivation
The string 010100 can be generated by recursively decomposing it around pairs of 0s:
010100 using the grammar \(S\rightarrow\varepsilon\mid S1\mid S0S0\).The construction used to derive the string mirrors the cases used in the inductive completeness proof.
The larger grammar hierarchy
Context-free grammars are more powerful than regular expressions, but they still impose a major restriction: the left-hand side of every rule must be one variable.
More general grammar systems relax this restriction:
| Grammar type | Representative production |
|---|---|
| Context-free | \(A\rightarrow BCD\) or \(A\rightarrow a\) |
| Context-sensitive | \(XAY\rightarrow XBCDY\) |
| Unrestricted | \(XAY\rightarrow BCD\) |
The next machine model—the pushdown automaton—will explain operationally why CFGs can handle nested and matched structures that finite automata cannot.
Check your understanding
- How is a grammar a recursive definition of a language?
- What is the difference between a terminal and a variable?
- Why is \(\varepsilon\) not a terminal symbol?
- What does a parse tree capture that a derivation sequence may obscure?
- How can two different derivation orders represent the same parse tree?
- What makes a grammar ambiguous?
- Why are CFLs not closed under intersection or complement?
- Why must grammar correctness be proved in two directions?