In the previous chapter, the pumping lemma showed us that a simple language like { anbn } is not regular. Finite automata cannot match an unbounded number of opening symbols with the same number of closing symbols.
But matching is everywhere in computer science: brackets in an expression, { and } in a C program, opening and closing tags in HTML. We need a more powerful way to describe languages. That is the job of context-free grammars.
A context-free grammar (CFG) is a finite set of rewriting rules that generates strings by repeatedly replacing a single variable with a string of variables and terminals. The languages generated by CFGs are called context-free languages (CFLs).
In this chapter we will define CFGs formally, see how they generate strings, and practise the most important exam skill: designing a grammar for a given language, and finding the language of a given grammar. Every grammar in this chapter was checked by a program against its language definition on all strings up to length 10 to 12.
The Idea: Rules That Build Strings
A regular expression describes strings by patterns. A grammar describes them by rules of construction, like a recipe.
Here is a recipe for { anbn | n ≥ 0 }:
The empty string is in the language.
If some string is in the language, then putting an a in front and a b at the end gives another string in the language.
Written as a grammar:
S → aSb
S → εRead "S → aSb" as "S can be replaced by aSb". Starting from S and applying rules:
S ⇒ aSb ⇒ aaSbb ⇒ aaaSbbb ⇒ aaabbbEvery application of S → aSb adds exactly one a and one b, on opposite sides, so they always stay balanced. This "wrap around the middle" trick is exactly what a DFA cannot do, and it is the heart of most CFGs.
Formal Definition
A context-free grammar is a 4-tuple G = (V, T, P, S) where:
V is a finite set of variables (non-terminals),
T is a finite set of terminals, disjoint from V,
P is a finite set of productions, each of the form A → α with A ∈ V and α ∈ (V ∪ T)*,
S ∈ V is the start symbol.
For the anbn grammar: V = {S}, T = {a, b}, P = {S → aSb, S → ε}, start symbol S.
Notation conventions
Upper-case letters (A, B, S, …) are variables. Lower-case letters, digits and symbols (a, b, 0, +, …) are terminals.
Greek letters (α, β, γ) stand for strings of variables and terminals.
A → α | β is short for the two productions A → α and A → β. So S → aSb | ε is our grammar in one line.
A is the head (left side) of A → α; α is the body (right side).
Unless stated, the head of the first production is the start symbol.
Derivations and the language of a grammar
One derivation step: if A → γ is a production, then αAβ ⇒ αγβ. We replace one occurrence of a variable by the body of one of its productions.
⇒* means "in zero or more steps".
Any string α with S ⇒* α is a sentential form. A sentential form with no variables left is a sentence.
The language of G is L(G) = { w ∈ T* | S ⇒* w }: all strings of terminals derivable from the start symbol. A language is context-free if some CFG generates it.
In S ⇒ aSb ⇒ aaSbb ⇒ aabb, the strings S, aSb and aaSbb are sentential forms, and aabb is a sentence. The order in which variables are replaced, and the tree picture of a derivation, are the topic of the next chapter, Derivations, Parse Trees & Ambiguity.
Why "context-free"?
The head of every production is a single variable. Whenever A appears in a sentential form, we may replace it using A → α, no matter what symbols surround it. Its context does not matter.
Compare a context-sensitive rule such as aAb → aγb, which may rewrite A only when it sits between a and b. Such grammars are more powerful; they appear in the Chomsky Hierarchy & Linear Bounded Automata chapter.
Classic Examples
Example 1: Palindromes over {a, b}
A palindrome is either empty, a single symbol, or a palindrome wrapped in the same symbol on both sides:
S → aSa | bSb | a | b | εDerivation of abbba:
S ⇒ aSa ⇒ abSba ⇒ abbba (last step uses S → b)Remove S → ε and you get only odd-length palindromes; remove S → a | b and you get only even-length palindromes (the language { wwR }).
Example 2: Balanced parentheses
A balanced string is empty, or a balanced string inside a pair of brackets, or two balanced strings side by side:
S → (S) | SS | εS ⇒ SS ⇒ (S)S ⇒ ()S ⇒ ()(S) ⇒ ()((S)) ⇒ ()(())Example 3: Arithmetic expressions
With terminals a (an operand), +, *, ( and ):
E → E + T | T
T → T * F | F
F → ( E ) | aE ⇒ E + T ⇒ T + T ⇒ F + T ⇒ a + T ⇒ a + T * F ⇒ a + F * F ⇒ a + a * F ⇒ a + a * aThis grammar is how real programming languages describe expressions. Notice how it builds operator precedence into its structure: * is generated "deeper" (by T) than + (by E). The next chapter explains why that matters.
Programming language manuals write grammars in BNF (Backus–Naur Form), which is the same idea with different punctuation: <expr> ::= <expr> "+" <term> | <term>. The Compiler Design tutorial builds parsers from such grammars.
How to Design a CFG
Most exam languages are built from a few patterns. Learn these and combine them.
Pattern | Trick | Example |
|---|---|---|
Two parts must match in count | Generate them together, from the outside in | anbn: S → aSb | ε |
Union L1 ∪ L2 | New start: S → S1 | S2 | see m ≠ n below |
Concatenation L1L2 | New start: S → S1S2 | anbncmdm |
Star L1* | S → S1S | ε | sequences of blocks |
Unmatched extra symbols | Add a rule that produces only one side | ambn, m ≥ n: S → aSb | aS | ε |
Ratio between counts | Produce symbols in that ratio per step | anb2n: S → aSbb | ε |
Nested pairs | The outer pair wraps the inner part | anbmcmdn |
After writing a grammar, always test it two ways: (1) can it generate the smallest strings of the language? (2) can it generate anything outside the language?
Solved Design Problems
Problem 1: { anb2n | n ≥ 0 }
Every a must come with two b's. Generate them in that ratio:
S → aSbb | εFor n ≥ 1 instead, change the base case: S → aSbb | abb.
Problem 2: { ambn | m ≥ n } and { ambn | m > n }
Match pairs with aSb, and allow extra a's with aS:
m ≥ n : S → aSb | aS | ε
m > n : S → aSb | aS | aFor m > n, the base case a guarantees at least one unmatched a. Why are extra a's always on the left? Because aS puts an a in front, before any b produced by later steps. So the order a…ab…b is never broken.
Problem 3: { ambn | m ≠ n }
m ≠ n means m > n or m < n. Write a grammar for each and take the union:
S → A | B
A → aAb | aA | a (m > n)
B → aBb | Bb | b (m < n)Problem 4: { aibjck | j = i + k }
Split the b's: aibi+kck = (aibi)(bkck). That is a concatenation of two matching languages:
S → AB
A → aAb | ε
B → bBc | εProblem 5: { aibjck | i = j + k }
Now split the a's: aj+kbjck = ak(ajbj)ck. The c's match the outer a's, so they are generated first, from the outside:
S → aSc | B
B → aBb | εProblem 6: { anbmcmdn } versus { anbncmdm }
a^n b^m c^m d^n (nested): S → aSd | A A → bAc | ε
a^n b^n c^m d^m (side by side): S → AB A → aAb | ε B → cBd | εBoth are context-free because the matched pairs are either nested or side by side. If they cross, as in { anbmcndm }, the language is not context-free. That is proved in the Pumping Lemma for Context-Free Languages chapter.
Problem 7: { aibjck | i = j or j = k }
Union of two concatenations:
S → XC | AY
X → aXb | ε (a^i b^i)
C → cC | ε (any c's)
A → aA | ε (any a's)
Y → bYc | ε (b^j c^j)Problem 8: equal number of a's and b's
L = { w ∈ {a,b}* | #a(w) = #b(w) }. The symbols can appear in any order, so "wrap around the middle" alone is not enough.
S → aSbS | bSaS | εWhy it works. Each production adds one a and one b, so every generated string is balanced. Conversely, take any non-empty balanced w that starts with a. Scan w from the left, keeping the count (#a − #b). It starts at +1, and it reaches 0 for the first time right after some b. So w = a u b v, where u is balanced (the count returned to the level it had) and v is balanced (the whole string is). By induction, u and v come from S, and S → aSbS builds w. The case of w starting with b is symmetric.
Another correct grammar is S → aSb | bSa | SS | ε.
Problem 9: { aibj | j ≤ i ≤ 2j }
Each b should be matched by either one a or two a's:
S → aSb | aaSb | εIf x steps use aSb and y steps use aaSb, we get ax+2ybx+y, and indeed j = x + y ≤ x + 2y ≤ 2x + 2y = 2j. Conversely, any i, j with j ≤ i ≤ 2j is reached with y = i − j and x = 2j − i.
Finding the Language of a Given Grammar
The reverse skill: list the shortest strings, spot the pattern, then argue why. A few common ones:
Grammar | Shortest strings | Language |
|---|---|---|
S → aSa | bSb | a | b | a, b, aaa, aba, bab, bbb | odd-length palindromes |
S → aSb | ab | ab, aabb, aaabbb | anbn, n ≥ 1 |
S → aS | bS | b | b, ab, bb, aab, … | strings ending in b (regular!) |
S → aS | Sb | ε | ε, a, b, aa, ab, bb | a*b* (regular!) |
S → aSb | bSa | ε | ε, ab, ba, aabb, abab, baba, bbaa | even length, and the i-th symbol from the left differs from the i-th from the right |
S → aB | bA, A → a | aS | bAA, B → b | bS | aBB | ab, ba, aabb, abab, … | non-empty strings with #a = #b |
In the last grammar, A generates strings with exactly one more a than b's, and B strings with one more b. That invariant is the key to proving it.
Regular Languages Are Context-Free
Every regular language is context-free. Given a DFA, make a variable for each state, a production A → aB for each transition δ(A, a) = B, and A → ε for each final state A. This is exactly the right-linear grammar construction from the Regular Grammars chapter, and a right-linear grammar is a special CFG.
The containment is proper: anbn is context-free but not regular. And context-free languages have limits too: { anbncn } is not context-free (three counts cannot all be matched by wrapping).
Feature | Regular grammar | Context-free grammar |
|---|---|---|
Production form | A → aB | a | ε (right-linear) | A → any string of variables and terminals |
Machine | Finite automaton | Pushdown automaton (finite automaton + stack) |
Can match unbounded pairs? | No | Yes, if nested or side by side |
Example | a*b* | anbn, balanced brackets |
Chomsky type | Type 3 | Type 2 |
The machine model for CFGs, the pushdown automaton, is the subject of the Pushdown Automata chapter.
Where CFGs Are Used
Programming languages: the syntax of languages such as C and Java is specified by CFGs in their official standards (Python's current parser uses a closely related PEG grammar); parser generators such as Yacc/Bison take a CFG as input.
Markup and data formats: nested HTML/XML elements and JSON objects are context-free structures.
Natural language processing: sentence structure (noun phrase, verb phrase) is often modelled with CFGs.
Common Mistakes
Generating a and b independently. S → aS | Sb | ε looks like it builds anbn, but it generates a*b*: nothing ties the counts together. Counts are matched only when one production adds both symbols.
Forgetting the base case. S → aSb alone generates no string at all, because S never disappears.
Wrong base case. S → aSb | ε includes ε; if the language requires n ≥ 1, use S → aSb | ab.
Generating extra strings. Always try to break your grammar: derive a few strings and confirm each one is in the language.
Confusing nested and crossing matches. anbmcmdn is context-free; anbmcndm is not.
Thinking a CFG always describes a non-regular language. Many CFGs (like S → aS | bS | b) generate regular languages.
GATE and Interview Questions
Q1. What is the language generated by S → aSbb | ε?
{ anb2n | n ≥ 0 }. Each step adds one a on the left and two b's on the right.
Q2. Write a CFG for { aibjck | i + k = j }.
aibi+kck = (aibi)(bkck), so S → AB, A → aAb | ε, B → bBc | ε.
Q3. Which grammar generates { ambn | m > n }? (a) S → aSb | a (b) S → aSb | aS | a (c) S → aS | Sb | a (d) S → aSb | ε
(b). (a) gives only an+1bn, missing for example aaa. (c) gives a+b*, which includes abb. (d) gives anbn.
Q4. Is { anbmcmdn | n, m ≥ 0 } context-free? Give a grammar.
Yes, because the pairs are nested: S → aSd | A, A → bAc | ε.
Q5. Why is the expression grammar E → E + T | T, T → T * F | F, F → (E) | a preferred over E → E + E | E * E | (E) | a?
Both generate the same language, but the second one is ambiguous (a + a * a has two parse trees), and it does not encode precedence or associativity. The first one forces * to bind tighter than + and makes both operators left-associative. Details are in the next chapter.
Q6. Is every context-free language regular? Is every regular language context-free?
No to the first (anbn is a counterexample). Yes to the second: any DFA can be turned into a right-linear grammar, which is a CFG.
Q7. In G = (V, T, P, S), why must V and T be disjoint?
A symbol must be either something that can still be rewritten (variable) or a final output symbol (terminal). If a symbol were both, we could not tell when a derivation has finished and produced a string of the language.
Summary
A CFG is G = (V, T, P, S) with productions of the form A → α, where A is a single variable.
A derivation replaces one variable at a time. L(G) is the set of terminal strings derivable from S.
The key power of CFGs is matching: rules like S → aSb generate paired symbols together, which no finite automaton can do.
Design with patterns: wrap for matching, union with S → S1 | S2, concatenation with S → S1S2, extra symbols with one-sided rules.
Regular languages ⊂ context-free languages. Nested or side-by-side matches are context-free; crossing matches and three-way matches (anbncn) are not.
Always test a grammar both ways: it must generate every string of the language and nothing else.
A regular expression describes a pattern; a context-free grammar describes a structure.