08 Proving Non-Regularity

We continue our exploration of finite automata, focusing on the crucial topic of proving non-existence. We’ve established that finite automata can recognize a certain class of languages, the regular languages. But what are their limits?

We have three primary techniques to prove that a language is not regular. All three are indirect proofs by contradiction. They all start with the same premise: “Assume the language is regular.” This assumption implies the existence of a finite automaton, and it’s the finiteness of this automaton that we will exploit to derive a contradiction.

Recap: Lemma 3.3

Our first technique, which we covered in detail, was Lemma 3.3. Let’s quickly recap its core idea.

Lemma 3.3: If a language is regular, then there exists a DFA for it. If two different words, $x$ and $y$, drive this DFA to the same state $p$, then for any suffix $z$, the words $xz$ and $yz$ must also end in the same state. Consequently, either both $xz$ and $yz$ are in the language, or neither is.

$$xz\in L(A)⟺yz\in L(A)$$

We used this by finding a set of words larger than the number of states, guaranteeing a collision (two words landing in the same state), and then choosing a “killer suffix” $z$ that made one word valid and the other invalid, leading to a contradiction.

The Pumping Lemma for Regular Languages

Today, we introduce the second, and perhaps most famous, technique: the Pumping Lemma. The underlying principle is the same, exploiting the finite memory of the automaton, but the approach is slightly different. Instead of looking at two different words, we look at one single, very long word.

Lemma 3.4 (Pumping Lemma for Regular Languages): Let $L\subseteq {\Sigma }^{\ast }$ be a regular language. Then there exists a constant $n_0\in \mathbb{N}$ (the “pumping length”) such that every word $w\in {\Sigma }^{\ast }$ with $|w|\ge n_0$ can be decomposed into three parts, $w=yxz$, satisfying three conditions:

1. The prefix and the pumpable part are short: $|yx|\le n_0$.
2. The pumpable part is not empty: $|x|\ge 1$.
3. The word can be “pumped”: For all $k\in {\mathbb{N}}_0$, the word $y{x}^{k}z$ is either always in $L$ or never in $L$. Formally: $$\{y{x}^{k}z\mid k\in {\mathbb{N}}_0\}\subseteq L\text{or}\{y{x}^{k}z\mid k\in {\mathbb{N}}_0\}\cap L=\varnothing$$

The Proof Idea

The proof is beautifully intuitive.

1. Assume $L$ is regular. This means there exists a DFA $A$ with a finite number of states. Let’s set the pumping length $n_0$ to be the number of states in this automaton, $n_0=|Q|$.
2. Take a long word. Choose any word $w$ with length $|w|\ge n_0$.
3. The Pigeonhole Principle again. As the automaton processes the first $n_0$ symbols of $w$, it passes through $n_0+1$ configurations (the start configuration plus one for each symbol read). Since there are only $n_0$ states, it must visit at least one state twice within this prefix.
4. Finding the loop. This repeated state creates a loop in the computation path.
5. Decomposition. We can now decompose the word $w$ into $yxz$:
   • $y$ is the prefix that takes the automaton from the start state to the first time it enters the repeated state.
   • $x$ is the substring that takes the automaton around the loop and back to the repeated state.
   • $z$ is the rest of the word.
6. Checking the conditions:
   • (i) $|yx|\le n_0$: The loop must occur within the first $n_0$ symbols, so this holds.
   • (ii) $|x|\ge 1$: A loop requires at least one transition, so at least one symbol is read.
   • (iii) Pumping: We can traverse the $x$ loop zero times (skipping it), once (the original word), twice, or any number of times. Since the rest of the computation ($z$) starts from the same state in every case, the final outcome (accept or reject) must be the same for all pumped versions of the word.

Applying the Pumping Lemma: The Game

Using the Pumping Lemma to prove a language is not regular is like playing a game against an adversary.

1. The Adversary’s Move: The Pumping Lemma states that if $L$ is regular, there exists a pumping length $n_0$. To prove it’s not regular, we must show that for any possible $n_0$ the adversary gives us, we can win.
2. Our Move: The lemma says for all words $w$ with $|w|\ge n_0$. We only need to find one clever counterexample word $w$ (that depends on $n_0$) to break the lemma.
3. The Adversary’s Move: The lemma says there exists a decomposition $w=yxz$. We must show that for all possible decompositions that satisfy conditions (i) and (ii), we can find a contradiction.
4. Our Move: We show that for any such decomposition, condition (iii) fails. We find a pumping factor $k$ (often $k=0$ or $k=2$) such that $y{x}^{k}z$ has a different membership status in $L$ than the original word $w$.

Example 1: $L=\{a^n{b}^n\mid n\in \mathbb{N}\}$ is not regular

Proof by Contradiction:

1. Assume $L$ is regular. By the Pumping Lemma, there exists a pumping length $n_0$.
2. We choose a word. We need a word $w\in L$ with $|w|\ge n_0$. A strategic choice is $w=a^{n_0}{b}^{n_0}$.
3. The adversary gives a decomposition. The lemma guarantees that $w$ can be split into $yxz$ such that:
   • (i) $|yx|\le n_0$
   • (ii) $|x|\ge 1$
4. We find the contradiction. From condition (i), we know that the substring $yx$ must be part of the initial block of $a$‘s. This means $y$ and $x$ consist only of $a$‘s. From condition (ii), we know $x$ contains at least one $a$. So, $x=a^l$ for some $l$ where $1\le l\le n_0$.
5. Now we pump. Let’s choose $k=2$. The new word is $w^{\prime }=y{x}^{2}z$. $$w^{\prime }=yxxz=a^{n_0+l}{b}^{n_0}$$ Since $l\ge 1$, the number of $a$‘s is not equal to the number of $b$‘s. Therefore, $w^{\prime }\notin L$.
6. This is a contradiction. The original word $w$ was in $L$, but the pumped word $w^{\prime }$ is not. This violates condition (iii) of the Pumping Lemma.
7. Conclusion: Our initial assumption was wrong. $L$ is not regular.

Example 2: $L=\{0^{n^2}\mid n\in \mathbb{N}\}$ is not regular

Proof by Contradiction:

1. Assume $L$ is regular. There exists a pumping length $n_0$.
2. We choose a word. Let’s pick $w=0^{n_0^2}$. This word is in $L$ and $|w|\ge n_0$.
3. The adversary gives a decomposition $w=yxz$ where $|yx|\le n_0$ and $|x|\ge 1$.
4. We find the contradiction. The substring $x$ must be a block of zeros, so $x=0^l$. From the conditions, we know $1\le l\le n_0$.
5. Let’s pump with $k=2$. The new word is $w^{\prime }=y{x}^{2}z=0^{n_0^2+l}$.
6. Is the length of this new word a perfect square?
   • The current length is $n_0^2+l$.
   • The next perfect square after $n_0^2$ is $(n_0+1{)}^2=n_0^2+2n_0+1$.
   • We know $1\le l\le n_0$. Therefore, $n_0^2<n_0^2+l<(n_0+1{)}^2$.
   • The length $n_0^2+l$ lies strictly between two consecutive perfect squares, so it cannot be a perfect square itself. Thus, $w^{\prime }\notin L$.
7. This is a contradiction. $w\in L$ but $w^{\prime }\notin L$.
8. Conclusion: $L$ is not regular.

A Third Technique: Kolmogorov Complexity

Our third method for proving non-regularity is perhaps the most elegant. It connects the finite memory of automata directly to the information content of strings.

Theorem 3.1: Let $L\subseteq \{0,1{\}}^{\ast }$ be a regular language. For any prefix $x\in \{0,1{\}}^{\ast }$, consider the “suffix language” $L_x=\{y\in \{0,1{\}}^{\ast }\mid xy\in L\}$. Then there exists a constant $c$ such that for all $x,y\in \{0,1{\}}^{\ast }$:

$$\text{If }y\text{ is the }n\text{-th word in }{L}_x,\text{ then }K(y)\le \lceil {\log }_2(n+1)\rceil +c$$

In simpler terms: for any regular language, the words that can follow a given prefix to form a valid string cannot be too complex. Their Kolmogorov complexity is bounded by the logarithm of their rank.

Proof Idea

If $L$ is regular, there is a DFA $A$ for it. For any prefix $x$, the automaton ends up in some state $q=\hat{\delta }(q_0,x)$. The language $L_x$ is then the set of all words that drive the automaton from state $q$ to an accepting state. This means $L_x$ is itself a regular language, accepted by an automaton that is identical to $A$ but with $q$ as its start state.

We can write a program that finds the $n$-th word $y$ in $L_x$. This program needs:

1. The description of the automaton $A$ (constant size).
2. The description of the start state $q$ (constant size).
3. The integer $n$ (size $\log n$).

The program simulates $A$ starting from state $q$ on all possible strings in canonical order, counting until it finds the $n$-th one that is accepted. The length of this program gives us the upper bound on $K(y)$.

Application: $L=\{0^n{1}^n\mid n\in \mathbb{N}\}$ is not regular (again)

Proof by Contradiction:

1. Assume $L$ is regular. Then Theorem 3.1 holds.
2. Consider a class of prefix languages. For every $m\in \mathbb{N}$, let’s look at the prefix $x=0^m$. The corresponding suffix language is: $$L_{0^m}=\{y\in \{0,1{\}}^{\ast }\mid 0^{m}y\in L\}$$ By the definition of $L$, the only word that can follow $0^m$ to form a valid string is $1^m$. So, $L_{0^m}=\{1^m\}$.
3. Find the first word. For each of these languages, the first word is $y=1^m$. ($L_{0^n}=\{1^n,01^{m+1},001^{m+2},\dots \}$) So, for $n=1$, we can apply the theorem.
4. Apply the theorem. According to Theorem 3.1, there is a constant $c$ such that for all $m$: $$K(1^m)\le \lceil {\log }_2(1+1)\rceil +c=1+c=c^{\prime }$$
5. The Contradiction. This implies that all strings of the form $1^m$ have a constant, bounded Kolmogorov complexity. But this is absurd. The set $\{1^m\mid m\in \mathbb{N}\}$ is an infinite set of distinct strings. There can only be a finite number of programs of length less than or equal to $c^{\prime }$. Therefore, there must be strings $1^m$ whose complexity is much larger than $c^{\prime }$.
6. Conclusion: Our assumption that $L$ is regular leads to a contradiction. $L$ is not regular.