2.5Recognising non-regular languages
The idea
To spot non-regular languages, look for anything that needs to count without a bound or compare two unbounded things.
Think of it like this: A cashier who can only remember the last three transactions cannot check a day's total.
Why it exists
Most pumping-lemma questions are classification: which of these four languages is regular?
How it works
- Counting a block then matching another block (aⁿbⁿ) → not regular.
- Copying or reversing (ww, wwᴿ) → not regular.
- Squares, powers of 2, primes in unary → not regular.
- A language with finitely many Myhill–Nerode classes is regular; every finite language is regular.
Worked example: The tricky regular one
{ w ∈ {0,1}* : #01 = #10 } is regular: the counts of 01 and 10 differ by at most one, and are equal exactly when the first and last symbols match.
Now play with it
- →Answer the regular / not regular quiz and read the reasons.
Regular or not regular? · question 1 of 8
{ aⁿbⁿ : n ≥ 0 }
Check yourself
Which language over {a,b} is regular?
Exam notes (the dense version)
A language needs unbounded memory if it compares or counts: aⁿbⁿ, ww, palindromes, aⁿ² , primes, equal numbers of a and b. By Myhill–Nerode, L is regular iff it has finitely many equivalence classes. Every finite language is regular; a subset of a regular language need not be.
Previous year questions: Regular Expressions & Regular Languages (14)
PYQs are grouped by topic, so this is the full set for Regular Expressions & Regular Languages; try the ones that match this subtopic. Open all 14 on the topic page.