Chapter 17 of 34

Context-Free Grammars

On this page

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 ⇒ aaabbb

Every 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 ) | a
E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ a + T ⇒ a + T * F ⇒ a + F * F ⇒ a + a * F ⇒ a + a * a

This 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 | a

For 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.