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 of bs.
• All the as must come before all the bs.

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 S with a S b → this adds one ‘a’ in the front and one ‘b’ at the end
• Or replace S with ε → 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
→ aaabbb

Each 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 of bs matches the number of as.

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 b

which 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

examhopeinfo@gmail.com

Administrator

Visit Website View All Posts