Context-Free Grammar for a Nonregular Language
🌱 The Classic Nonregular Language: L = { aⁿ bⁿ | n ≥ 0 }
This language contains strings like:
ε
ab
aabb
aaabbb
aaaabbbb
...The rule is simple:
- The number of
as must be equal to the number ofbs. - All the
as must come before all thebs.
On the surface it seems easy, but DFAs cannot remember how many as they have seen.
They have no stack or memory.
But a CFG can build this language beautifully.
🎯 A Simple CFG for L = { aⁿ bⁿ }
We can define it with one elegant rule:
S → aSb | εLet’s rewrite this in plain English:
- Replace
Switha S b→ this adds one ‘a’ in the front and one ‘b’ at the end - Or replace
Swithε→ this is the base case when n = 0
With just this one rule, you can generate strings with equal numbers of as and bs.
💡 How the Grammar Builds Strings Step-by-Step
Let’s generate the string aaabbb.
S
→ aSb
→ aaSbb
→ aaaSbbb
→ aaabbbEach step adds one a and one b — perfectly balanced.
🧱 Why This Language Is Nonregular
Try to imagine a DFA recognizing this pattern:
- It reads
as first. - It must remember how many
as were seen. - When it switches to
bs, it must check that the number ofbs matches the number ofas.
A DFA has no memory stack.
It cannot “count” arbitrary lengths.
A CFG can, because its production rules expand symmetrically — adding pairs.
🖼 Parse Tree Diagram for “aabb”
Below is a clear, easy-to-read parse tree:
S
____|____
a Sb
/ \
a S b
|
εIf we read the leaves from left to right, we get:
a a b bwhich forms the string aabb.
🌟 Why This Example Is So Important
This language is often used in textbooks, classes, and exams because:
✔ It is one of the simplest examples of a nonregular language
It passes the pumping lemma test for nonregularity.
✔ It demonstrates the true strength of CFGs
CFGs handle nested, balanced, or counted structures—things regular languages cannot do.
✔ It connects directly to Pushdown Automata (PDA)
A PDA can accept this language by pushing as onto the stack and popping one for each b.
✔ It forms the foundation for understanding programming language syntax
Matching parentheses
Matching begin-end blocks
Matching HTML tags
All require this kind of nested structure.
About the Author
