Proving Nonregularity

Fooling sets

A nonregular language

During the second lecture, we learned the definition of regular languages as those built up from simpler finite languages using a few simple constructions. As has happened every time I’ve taught this course, somebody asked if every language is regular. It turns out the answer is no. In particular…

Theorem: The language $L = \{0^n 1^n \mid n \geq 0\}$ is not regular.

The proof relies on Kleene’s theorem. If $L$ is regular, than there should be a DFA that accepts $L$ . We’re going to argue that no such DFA exists. The high level intuition behind the argument is that any DFA accepting $L$ must be able to count the 0s as they are encountered while reading the input string. However, storing an arbitrarily high count requires an arbitrarily large number of states, and every DFA has a fixed finite set of states by definition.

Let’s make the idea more precise. Suppose there is a DFA $M = (Q, \delta, s, A)$ that accepts $L$ , and consider any two strings $x = 0^i$ and $y = 0^j$ where $i \neq j$ . Also, let $z = 1^i$ . We have $xz = 0^i 1^i \in L$ and $yz = 0^j 1^i \notin L$ .

Suppose we feed $xz$ to $M$ . The machine goes to some state $\delta^*(s, x)$ and then continues on to $\delta^*((\delta^*(s, x), z)) \in A$ , because $xz \in L$ . Suppose we feed $yz$ to $M$ . The machine goes to some state $\delta^*(s, y)$ and then continues on to $\delta^*((\delta^*(s, y), z)) \notin A$ , because $yz \notin L$ .

Therefore, $\delta^*((\delta^*(s, x), z)) \neq \delta^*((\delta^*(s, y), z))$ , implying $\delta^*(s, x) \neq \delta^*(s, y)$ . DFA $M$ must have at least two distinct states in order to successfully accept $xz$ while also rejecting $yz$ . These states are needed to distinguish between $x$ and $y$ .

Now consider the infinite set of strings $F = \{0^i \mid i \geq 0\}$ . By the above argument, every choice of $x \in F$ must lead to a distinct state $\delta^*(s, x)$ . Therefore, $M$ has to have an infinite set of states, which is impossible, because $M$ is a deterministic finite-state automata. With a bit more scaffolding, we can apply the ideas of the above proof to even more languages that are not regular.

Using fooling sets

Fix an alphabet $\Sigma$ , let $L$ be some language over $\Sigma$ , and let $x$ and $y$ be two strings over $\Sigma$ . One, both, or neither of $x$ and $y$ may be in $L$ . A string $z$ is a distinguishing suffix of $x$ and $y$ with respect to $L$ if exactly one of $xz$ or $yz$ is in $L$ . As shown above, if $x$ and $y$ are distinguishable by any suffix $z$ , then a DFA accepting $L$ must send $x$ and $y$ to distinct states. Otherwise, $xz$ and $yz$ would both go to the same state and they would both be accepted or both be rejected.

A set $F$ of strings is a fooling set for language $L$ if every pair of strings in $F$ has some distinguishing suffix with respect to $L$ . For example, let $L$ be the language represented by the regular expression $(0+1)^* (00 + 11) (0 + 1)^*$ , and let $F = \{\varepsilon, 0, 1, 00\}$ . Then,

$\varepsilon$ and $00$ are distinguished by $\varepsilon$ , because $\varepsilon \varepsilon = \varepsilon \notin L$ but $00 \varepsilon = 00 \in L$ .
$0$ and $00$ are distinguished by $\varepsilon$ .
$1$ and $00$ are distinguished by $\varepsilon$ .
$\varepsilon$ and $0$ are distinguished by $0$ .
$\varepsilon$ and $1$ are distinguished by $1$ .
$0$ and $1$ are distinguished by $1$ .

Any DFA for this language must have at least $4$ states, because no two members of $F$ can go to the same state. In general:

Theorem (Myhill-Nerode): For any language $L$ , the minimum number of states in a DFA accepting $L$ is ~~at least~~ equal to¹ the maximum size of a fooling set for $L$ .

A DFA cannot have an infinite set of states. Therefore, if $L$ has an infinite fooling set, then $L$ is not regular.

I’ve only argued that the DFA needs at least $|F|$ states. See Erickon’s Models Section 3.9 for a proof that $|F|$ states is enough.

Theorem: The language $L = \{0^n 1^n \mid n \geq 0\}$ is not regular (again.)

Proof: Consider the infinite set $F = \{0^i \mid n \geq 0\}$ , i.e., $F = 0^*$ .

Let $x$ and $y$ be distinct strings in $F$ .
By definition of $F$ , string $x = 0^i$ and string $y = 0^j$ for some integers $i \neq j$ .

Let $z = 1^i$ .
Then $xz = 0^i 1^i \in L$ .
But $yz = 0^j 1^i \notin L$ , because $i \neq j$ .
So $z$ distinguishes $x$ and $y$ .

Because $x$ and $y$ are arbitrary strings in $F$ , every pair of strings in $F$ has a distinguishing suffix.
We conclude $F$ is a fooling set for $L$ .
$F$ is also infinite, so $L$ cannot be regular.

This example demonstrates a useful rule of thumb: If intuition suggests your automaton needs to maintain an unbounded count (say, for the number of 0s you’ve seen), that count can serve as the basis for a fooling set of the form $\{0^i \mid i \geq 0\}$ or something similar. The distinguishing suffixes show how you’re forced to use the counter.

Theorem: The set of palindromes $L = \{w \mid w = \text{rev}(w)\}$ is not regular.

Intuitively, it should be even harder to design a DFA than last time, because we need to keep track of not just a count, but a whole substring and guess when it’s time to read it in reverse. But even if we know the substring is mostly a bunch of 0s, that’s still pretty hard to keep track of.

Proof: Consider the infinite set $F = \{0^i 1 \mid i \geq 0\}$ .

Let $x$ and $y$ be distinct strings in $F$ .
Then $x = 0^i 1$ and $y = 0^j 1$ for some $i \neq j$ .

Let $z = 0^i$ .
Then $xz = 0^i 1 0^i \in L$ .
But $yz = 0^j 1 0^i \notin L$ , because $i \neq j$ .
So $z$ distinguishes $x$ and $y$ .

Therefore, $F$ is a fooling set for $L$ .
$F$ is also infinite, so $L$ is not regular.

This example demonstrate another important idea behind choosing a fooling set: You get to choose it, and you’re free to impose additional structure on the subset of the language you consider if it’s convenient. The only strings in $L$ we really considered here are those of the form $0^i 1 0^i$ , but that was enough, because it suddenly felt like we were counting again.² And that single $1$ there was convenient, because it prevented coincidentally even length strings of 0s from being acceptable even when we didn’t want them to be.

Remember that the goal is to find some infinite set of distinguishable strings, not to find every set of distinguishable strings.

We could have gone with $F = \{0^i \mid i \geq 0\}$ as instead, setting $z = 10^i$ for each $x = 0^i$ . There ~~may~~ will be several infinite fooling sets for any nonregular language, because any infinite subset of an infinite fooling set is also an infinite fooling set.

Theorem: The language $L = \{0^{2^n} \mid n \geq 0\}$ it not regular.

We could go with $F = 0^*$ again, but then we’d need to do some math to find a good distinguishing suffix $z$ . Instead, observe that when ordered by length, consecutive strings of $L$ differ in a very predictable way.

Proof: Consider the infinite set $F = L$ .

Let $x$ and $y$ be distinct strings in $F$ .
Then $x = 0^{2^i}$ and $y = 0^{2^j}$ for some $i \neq j$ .

Let $z = 0^{2^i}$ .
Then $xz = 0^{2^i + 2^i} = 0^{2^{i+1}} \in L$ .
But $yz = 0^{2^i + 2^j} \notin L$ .
So $z$ distinguishes $x$ and $y$ .

Therefore, $F$ is an infinite fooling set of $L$ , and $L$ is not regular.

Proving nonregularity via reductions

There’s another strategy for proving nonregularity of certain languages that isn’t quite as powerful, but it may be more straightforward. It essentially boils down to a short proof by contradiction.

Suppose we have a language $L$ that we believe is nonregular. We assume to the contrary that $L$ is regular and then build a known nonregular language using the closure rules from the previous lecture (if another language is needed, we use a regular one.) In other words, we reduce the construction of the known nonregular language to our candidate language $L$ .

Theorem: The language $L = \Sigma^* \setminus \{0^n 1^n \mid n \geq 0\}$ is not regular.

Proof: Suppose for the sake of contradiction that $L$ is regular.
Then its compliment $\overline{L} = \Sigma^* \setminus L = \{0^n 1^n \mid n \geq 0\}$ is regular.
But we just proved $\overline{L}$ is not regular, giving us a contradiction.
We conclude that $L$ is not regular after all.

Here’s a slightly more complicated example.

Theorem: The language $L$ of binary strings with an equal number of 0s and 1s is not regular.

Proof: Suppose for the sake of contradiction that $L$ is regular.
The language (represented by) $0^*1^*$ is regular (because I defined it using a regular expression.)
Therefore, the language $L \cap 0^*1^* = \{0^n 1^n \mid n \geq 0\}$ is regular, because regularity is closed under intersection.
But we just proved $\{0^n 1^n \mid n \geq 0\}$ is not regular, giving us a contradiction.
We conclude that $L$ is not regular after all.

It’s important to keep straight the direction of these reduction arguments. The new language $L$ of unclear regularity is being used to construct a known nonregular language. It turns out that keeping the direction of these kinds of arguments clear is going to be a common refrain of mine in the last few weeks of this course as well.

So naturally, you’ll have forgotten that I brought it up now, and I cannot blame you.

For example, the languages $L = \{0^n 1^n \mid n \geq 0\}$ and $\overline{L} = \Sigma^* \setminus L$ are both nonregular as we’ve seen. However, I cannot then claim that $L \cup \overline{L}$ is nonregular, because it’s equal to known regular language $\Sigma^*$ !

Finally, a word of warning in correspondence with normal course policy: If your nonregularity proof involves “the pumping lemma” or a “homomorphism”, you’d better explain what that is, prove it if you’re talking about the pumping lemma, explain why it helps with proving nonregularity, and cite the outside source you used.