CFG Examples
Let's build context-free grammars for several important languages. These examples show the expressiveness of CFGs and how they handle structures that regular expressions cannot.
Example 1: Balanced Parentheses
The language of balanced parentheses {(), (()), ((())), ()(), etc.} is a classic context-free language. A regular expression cannot count matching pairs, but a CFG can.
Grammar for balanced parentheses:
S → ( S ) | S S | ε
Derivation of "(())()":
S → S S → ( S ) S → ( ( S ) ) S → (()) S → (()) ( S ) → (())()
Key insight: The recursive S → ( S ) rule creates
matching pairs. The S → S S rule allows concatenation.Example 2: Arithmetic Expressions
CFGs are the standard way to define programming language syntax. Here's a grammar for simple arithmetic:
Grammar for arithmetic expressions:
E → E + T | E - T | T
T → T * F | T / F | F
F → ( E ) | number
Where number is a terminal representing any numeric value.
Precedence is encoded in the grammar:
* and / bind tighter than + and -
Parentheses override everything
Derivation of "2 + 3 * 4":
E → E + T → T + T → F + T → number + T
→ number + T * F → number + F * F
→ number + number * number
→ 2 + 3 * 4
The grammar naturally gives * higher precedence
because T (which handles *) is deeper in the hierarchy.Example 3: Palindromes over {a,b}
Palindromes (strings that read the same forwards and backwards) are context-free. The grammar uses recursion to mirror characters.
Grammar for palindromes over {a, b}:
S → aSa | bSb | a | b | ε
Derivation of "abba":
S → aSa → abSba → abba
Derivation of "aba":
S → aSa → aba
The recursion ensures characters are added symmetrically.Example 4: {a^n b^n | n >= 1}
A simple grammar that generates equal numbers of a's followed by b's:
Grammar:
S → aSb | ab
Derivation of "aaabbb":
S → aSb → aaSbb → aabbb? No —
S → aSb → aaSbb → aaaSbbb → aaabbb? No —
Let's be careful:
S → aSb → aabbb? No.
Correct:
S → aSb → aabbbb? No.
S → aSb (first step)
S → aSb → aabb (second step, S → ab)
Wait: S → aSb, then replace S with ab: a( ab )b = aabb ✓
For "aaabbb":
S → aSb → aaSbb → aaaSbbb → aaabbb ✓
(S → ab at the innermost step)