Nonregular Languages

The limits of finite memory and the pumping lemma

Beyond the regular languages

Every finite language is regular, and many infinite languages are regular. But the regular languages form only a proper subset of all possible languages.

Finite languages lie inside the regular languages, which lie inside the collection of all languages.

To understand why some languages are not regular, recall the central limitation of a DFA:

A DFA has a fixed, finite number of states, regardless of how long its input becomes.

A DFA can have as many states as its designer chooses, but once the machine is built, that number is fixed. It cannot allocate new memory as it reads a longer input.

What a DFA cannot remember

A state summarizes everything about the input prefix that may matter later. Because a DFA has finitely many states, it can remember only finitely many distinguishable situations.

This is enough for properties such as:

• whether the number of 1s read so far is even or odd;
• the remainder of a binary number modulo three;
• whether a fixed substring has appeared; or
• whether the input currently matches a fixed pattern.

It is not enough to retain an arbitrary, unbounded quantity exactly. For example, recognizing

\[ \{a^nb^n:n\ge 0\} \]

requires comparing an unbounded number of as with a later number of bs. A finite state cannot store every possible value of \(n\).

The language-recognition game

Imagine a game played for a fixed language \(A\):

1. Player 1 draws a DFA \(M\) claimed to recognize \(A\).
2. Player 2 searches for a string \(s\) that \(M\) classifies incorrectly:
   • \(s\in A\) but \(M\) rejects it, or
   • \(s\notin A\) but \(M\) accepts it.

If \(A\) is regular, Player 1 can choose a correct DFA and should win. If \(A\) is nonregular, every proposed DFA must fail on some string, so Player 2 should always be able to win.

The challenge is proving this against every possible DFA, not merely showing that one attempted design is incorrect.

Testing our intuition

Consider the following languages.

\(A=a^*b^*\)

This language is regular. A DFA only needs to distinguish three situations:

1. no b has appeared;
2. a b has appeared and only bs have followed; or
3. an illegal a has appeared after a b.

\(A=\{a^nb^n:n\ge0\}\)

This language is not regular. The machine would need to remember exactly how many as appeared so that it could compare that number with the later bs.

Strings with more as than bs

The language

\[ \{w\in\{a,b\}^*: \#_a(w)>\#_b(w)\} \]

is not regular. The difference between the two counts can grow without bound.

Binary numbers divisible by three

The language

\[ \{w\in\{0,1\}^*:w\text{ represents a binary number divisible by }3\} \]

is regular. The machine need not remember the entire number; it only needs its current remainder modulo three.

When a bit \(b\in\{0,1\}\) is appended to a binary number with remainder \(r\), the new remainder is

\[ (2r+b)\bmod 3. \]

Three states—one for each possible remainder—are therefore sufficient.

A three-state DFA tracking a binary number’s remainder modulo three.

This example illustrates an important distinction: an unbounded input does not necessarily require unbounded memory. Only the information relevant to future decisions must be retained.

Why a long computation must loop

Suppose a DFA has state set \(Q\) and reads an input whose length is at least \(|Q|\). During the computation, it visits more state positions than there are states available. By the pigeonhole principle, some state must be visited more than once.

A sufficiently long accepting computation contains a repeated state and therefore a loop.

We can divide the corresponding input into three pieces:

\[ s=xyz, \]

where:

• \(x\) leads from the start state to the repeated state;
• \(y\) labels a nonempty loop from that state back to itself; and
• \(z\) leads from the repeated state to an accepting state.

Because \(y\) is a loop, the machine can traverse it any number of times without changing where the rest of the computation begins. This observation leads to the pumping lemma.

The pumping lemma for regular languages

The pumping lemma formalizes the idea that a sufficiently long DFA computation must contain a repeatable loop.

Pumping Lemma. If \(A\) is a regular language, then there is an integer \(p\ge1\), called the pumping length, such that every string \(s\in A\) with \(|s|\ge p\) can be divided as

\[s=xyz\]

satisfying:

1. \(|y|>0\);
2. \(|xy|\le p\); and
3. \(xy^iz\in A\) for every integer \(i\ge0\).

The substring \(y\) corresponds to a loop among the first \(p\) input symbols. We may:

• pump down with \(i=0\), removing \(y\);
• leave the string unchanged with \(i=1\); or
• pump up with \(i>1\), repeating \(y\).

The statement applies only to strings of length at least \(p\). Short strings may never reach a repeated state.

The quantifiers matter

The pumping lemma has a specific logical structure:

\[ A\text{ regular} \Longrightarrow \exists p\ \forall s\ \exists x,y,z\ \forall i\ge0: \mathcal{P}(p,s,x,y,z,i), \]

where \(s\in A\), \(|s|\ge p\), \(s=xyz\), \(|xy|\le p\), \(|y|>0\), and \(xy^iz\in A\).

To prove a language nonregular, we negate the conclusion:

\[ \forall p\ \exists s\ \forall x,y,z\ \exists i\ge0: xy^iz\notin A. \]

This determines who chooses each object in the pumping-lemma game.

The pumping-lemma game

To show that \(L\) is nonregular:

1. Opponent chooses an arbitrary pumping length \(p>0\).
2. You choose a string \(s\in L\) with \(|s|\ge p\).
3. Opponent chooses a valid decomposition \(s=xyz\) satisfying \(|xy|\le p\) and \(|y|>0\).
4. You choose an integer \(i\ge0\) for which \(xy^iz\notin L\).

You must win for every pumping length and every valid decomposition. It is not enough to select a convenient \(y\) yourself.

Standard proof template

The pumping lemma is normally used in a proof by contradiction.

1. Assume \(L\) is regular.
2. Let \(p\) be the pumping length guaranteed by the lemma.
3. Choose a carefully designed \(s\in L\) with \(|s|\ge p\).
4. Consider an arbitrary valid split \(s=xyz\) with \(|xy|\le p\) and \(|y|>0\).
5. Use the restrictions on the split to determine what \(y\) can contain.
6. Choose an \(i\)—often \(0\) or \(2\)—that forces \(xy^iz\notin L\).
7. This contradicts the pumping lemma, so \(L\) is not regular.

The creative step is choosing \(s\) so that every valid \(y\) lies in a controlled portion of the string.

Example: \(\{a^nb^n:n\ge0\}\)

Theorem. The language

\[A=\{a^nb^n:n\ge0\}\]

is not regular.

Proof. Assume, for contradiction, that \(A\) is regular. Let \(p\) be its pumping length and choose

\[ s=a^pb^p. \]

Then \(s\in A\) and \(|s|=2p\ge p\).

Consider any decomposition \(s=xyz\) satisfying \(|xy|\le p\) and \(|y|>0\). The first \(p\) symbols of \(s\) are all as, so

\[ y=a^k \]

for some \(k\ge1\).

Pump down by choosing \(i=0\):

\[ xy^0z=xz=a^{p-k}b^p. \]

This string has fewer as than bs, so it is not in \(A\). That contradicts the pumping lemma. Therefore, \(A\) is not regular. \(\square\)

The original slide’s compact pumping-lemma proof for \(\{a^nb^n:n\ge0\}\).

Why this string works

The condition \(|xy|\le p\) forces \(y\) to occur entirely inside the initial block of as. Pumping therefore changes the number of as without changing the number of bs.

Example: more as than bs

Let

\[ L=\{w\in\{a,b\}^*: \#_a(w)>\#_b(w)\}. \]

A direct pumping argument is possible. Assume \(L\) is regular, let \(p\) be its pumping length, and choose

\[ s=a^{p+1}b^p. \]

Every valid \(y\) consists only of as. Pumping down removes at least one a, producing a string with at most as many as as bs. The pumped string is not in \(L\), contradicting the lemma.

Another elegant proof uses closure. If \(L\) were regular, then so would be

\[ L\cap a^*b^*. \]

That intersection contains exactly the strings \(a^mb^n\) with \(m>n\), which can then be shown nonregular with a controlled pumping argument.

A language that should not be attacked with pumping

The language of binary numbers divisible by three is regular, so no valid pumping-lemma contradiction can exist. Any attempted proof of nonregularity must contain an error—usually one of these:

• choosing the decomposition instead of handling every valid decomposition;
• selecting a string that is not in the language;
• ignoring the condition \(|xy|\le p\);
• choosing \(i\) before seeing the decomposition; or
• finding one decomposition that fails rather than proving all decompositions fail.

The pumping lemma can show that a language is not regular. It cannot prove that a language is regular.

Combining pumping with closure properties

Sometimes a language is awkward to pump directly. Closure properties can transform it into a simpler language.

If \(L\) is regular and \(R\) is regular, then the following are regular:

\[ \overline{L},\qquad L\cap R,\qquad L\cup R,\qquad L\setminus R. \]

This gives a useful proof pattern:

1. assume the target language \(L\) is regular;
2. combine \(L\) with a known regular language using a closure operation;
3. obtain a language \(K\) already known—or easily shown—to be nonregular; and
4. conclude that the assumption about \(L\) was false.

For example, intersection with a carefully chosen regular language can filter out irrelevant strings and leave a structured language such as \(\{a^nb^n:n\ge0\}\).

Complement can also help: because regular languages are closed under complement,

\[ L\text{ is regular}\iff\overline{L}\text{ is regular}. \]

If \(\overline{L}\) is easier to prove nonregular, then \(L\) must also be nonregular.

What the pumping lemma does not say

Avoid these common misinterpretations:

• It does not say every string in a regular language can be pumped—only sufficiently long strings.
• It does not say every decomposition works—only that at least one suitable decomposition exists when the language is regular.
• It does not let the prover choose \(x\), \(y\), and \(z\) in a nonregularity proof.
• A language satisfying a pumping-like property is not automatically regular; the lemma provides a necessary condition, not a sufficient one.
• Failure to find a contradiction does not prove regularity.

Regular languages: one-section summary

A language is a set of strings. It is regular exactly when it can be represented by any of these equivalent formalisms:

• a deterministic finite automaton;
• a nondeterministic finite automaton; or
• a regular expression.

To prove that a language is regular, construct one of these representations.

To prove that a language is nonregular, demonstrate that finite state is insufficient. The pumping lemma turns the unavoidable loops in long DFA computations into a formal contradiction technique.

The regular languages are only part of a larger landscape. More powerful machines will recognize some languages outside this class.

Check your understanding

1. Why can a DFA track a remainder modulo three but not an arbitrary counter?
2. Where do the three pieces \(x\), \(y\), and \(z\) appear in an accepting DFA computation?
3. Why must \(|y|>0\)?
4. Why is the restriction \(|xy|\le p\) essential in the proof for \(a^nb^n\)?
5. Who chooses the pumping decomposition in a proof of nonregularity?
6. Why can the pumping lemma refute regularity but not establish it?