Limitations of Regular Languages

Non-Regular Language

A non-regular language is a language that cannot be recognized by any Deterministic Finite Automaton (DFA), Non-deterministic Finite Automaton (NFA), or described by a regular expression. These languages require computational power beyond what finite memory (a finite number of states) can provide. An example is {a^n b^n | n ∈ ℕ}.

Why Not All Languages are Regular (Counting Argument)

There are uncountably many languages (as many as real numbers) over any alphabet, but only countably many regular expressions (or DFAs). This means there are far more languages than possible regular expressions, so most languages must be non-regular.

The Pumping Lemma (for Regular Languages)

The Pumping Lemma is a necessary condition for a language to be regular. It states: If a language L is regular, then there exists a pumping length p such that any string s in L with length |s| ≥ p can be divided into three parts s = xyz where:

1. |y| > 0 (the "pumpable" part is non-empty)

2. |xy| ≤ p (the first two parts are within the first p symbols)

3. For all i ≥ 0, the string xy^i z is also in L.

Pumping Lemma Logic (Contrapositive)

The Pumping Lemma is used to prove a language is NOT regular via its contrapositive: If for every possible pumping length p you can find some string s in L (with |s| ≥ p) that cannot be pumped (i.e., no division s=xyz satisfies all three conditions), then the language L is not regular.

Pumping Lemma: Condition 1 (|y| > 0)

Condition 1 (|y| > 0) means the middle part y you can repeat must contain at least one symbol. You cannot "pump" an empty substring. This ensures the pumping action actually changes the string.

Pumping Lemma: Condition 2 (|xy| ≤ p)

Condition 2 (|xy| ≤ p) means the part you will pump (y) must lie within the first p symbols of the chosen string s. This is crucial because it limits where the repeating pattern can be found, often forcing y to consist of only one type of symbol in proofs.

Pumping Lemma: Condition 3 (xy^i z ∈ L)

Condition 3 says that repeating (i > 1) or removing (i = 0) the middle part y must always produce a string that is still in the language L. If pumping a string creates a string not in L, you have found a contradiction, proving L is not regular.

Applying the Pumping Lemma: Example {a^n b^n}

To prove L = {a^n b^n | n ≥ 0} is not regular:

1. Assume L is regular. Let p be its pumping length.
2. Choose the string s = a^p b^p. This string is in L and |s| ≥ p.
3. By the lemma, s = xyz with |y|>0, |xy|≤p.
4. Since |xy|≤p, y must consist only of a's (it's in the first p symbols).
5. Pump y: Let i=2. The string xy^2 z has more a's than b's, so it's not in L.
6. Contradiction. Therefore, L is not regular.

The Core Idea Behind Pumping

The Pumping Lemma exploits the pigeonhole principle applied to DFAs. If a string is longer than the number of states p, by the time it is read, some state must be visited twice. The symbols read between these two visits form the substring y that can be repeated (pumped) because the loop can be traversed any number of times.

Pumping Lemma as a Necessary but Not Sufficient Condition

The Pumping Lemma is a necessary condition for regularity: if a language is regular, it must be pumpable. However, it is not sufficient: some non-regular languages can also be pumped. It is a tool for proving non-regularity, not for proving regularity.