14  Non-regularity

In this chapter we see some techniques useful to show that a language is not in \mathbf{Regular}. One technique (the fooling sets, see Section 14.1) is also useful to show lower bounds on the number of states of the minimum DFA accepting a regular language.

14.1 Non-regularity via fooling sets

The first technique we see is the use of fooling sets. This is useful to show that some given language L is not regular or that no DFA with few states can accept L.

Definition 14.1 (fooling set) Given a language L\subseteq \Sigma^*, a set F\subseteq \Sigma^* is a fooling set for L if for every x,y\in F with x\neq y there exists z\in \Sigma^* s.t. xz\in L and yz\notin L.

Theorem 14.1 If F is a fooling set for L, then there is no DFA A with strictly less than |F| states s.t. L=\mathscr{L}(A). In particular, if F is infinite then L\notin \mathbf{Regular}.

Assume, towards a contradiction, that there exists a DFA A with strictly less than |F| states and such that L=\mathscr{L}(A). Let q_0 be the initial state of A and q_0w be the state of A in which we end-up when reading the word w.

By the pigeonhole principle (see Chapter 2), there are exist x,y\in F with x\neq y s.t. q_0x=q_0y. Since F is a fooling set, exists z\in\Sigma^* s.t. xz\in L and yz\notin L. That is q_0xz is a final state and q_0yz is not a final state. Since q_0x=q_0y then q_0xz=q_0yz, and this gives the desired contradiction.

Theorem 14.1 is actually an if and only if but we are only interested in the implication useful to prove limitations of DFAs.

We can use it to prove that a language is not in \mathbf{Regular} as in the following example.

Example 14.1 L=\{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}\notin \mathbf{Regular}.

By Theorem 14.1, it is enough to construct an infinite fooling set for L. Consider F=\{\textcolor{darkred}{\mathtt{a}}^n :n\in \mathbb{N}\}. Given two distinct words x,y\in F we must have x=\textcolor{darkred}{\mathtt{a}}^n and y=\textcolor{darkred}{\mathtt{a}}^m with n\neq m. We can then choose z=\textcolor{darkred}{\mathtt{b}}^n. We have that xz=\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\in L and yz=\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^m\notin L (since n\neq m). That is F is a fooling set for L.

We can also use Theorem 14.1 to show that some automata is actually the smallest possible, as in the next examples.

Example 14.2 As a first example we show that the minimum DFA for the language L=\{w \in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\mathtt{value}_2(w)\in 3\mathbb N\} has at least 3 states. (Did you construct a minimal DFA for this language in Exercise 10.3?)

Consider the set F=\{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}},\textcolor{darkred}{\mathtt{10}}\}. We show that F is a fooling set. Let’s consider the different possibilities for x\neq y in F and for each of them a possible z to choose s.t. xz\in L and yz\notin L:

x y z
\textcolor{darkred}{\mathtt{0}} \textcolor{darkred}{\mathtt{1}} \textcolor{darkred}{\mathtt{0}}
\textcolor{darkred}{\mathtt{0}} \textcolor{darkred}{\mathtt{10}} \textcolor{darkred}{\mathtt{0}}
\textcolor{darkred}{\mathtt{1}} \textcolor{darkred}{\mathtt{10}} \textcolor{darkred}{\mathtt{1}}

A less trivial example is the following.

Example 14.3 Given n\in \mathbb N, consider the language L_n=\{x\textcolor{darkred}{\mathtt{a}}y :x,y\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* \land |y|=n\}\ . In Exercise 9.11, you constructed a DFA B with 2^{n+1} states s.t. \mathscr{L}(B)=L_n. We construct now a fooling set F for L_n of size 2^{n+1}. This, thanks to Theorem 14.1 implies that B must be minimal. Another consequence is that the DFA B obtained in Theorem 9.2, in the worst case, might be exponentially larger than the corresponding NFA A.

Take F=\{w\in\{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|=n+1\}. The set F clearly has the correct size, and we prove now it is a fooling set for L_n. Given distinct x,y\in F, let i the largest index s.t. x[i]\neq y[i]. W.l.o.g. let x[i]=\textcolor{darkred}{\mathtt{a}} and y[i]=\textcolor{darkred}{\mathtt{b}}. If i=1 (recall that we start numbering the positions in a word from 1), take z=\varepsilon, if i=2 take z=\textcolor{darkred}{\mathtt{a}}, and in general take z=\textcolor{darkred}{\mathtt{a}}^{i-1}. We have that xz has an \textcolor{darkred}{\mathtt{a}} in position n+1 from the end, while yz has a \textcolor{darkred}{\mathtt{b}} in position n+1 from the end. That is xz\in L_n while yz\notin L_n. This concludes the proof that F is a fooling set for L_n.

Notice that i being the largest index s.t. x[i]\neq y[i] is not important: any index i s.t. x[i]\neq y[i] would work as-well. And similarly z=\textcolor{darkred}{\mathtt{a}}^{i-1} is also not-important: any word z of length i-1 would also work.

Exercise 14.1 To make sure you understood the argument in Example 14.3, prove that F=\{w\in\{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|=n+2\} is not a fooling set for L_n by showing it does not match the definition of fooling set.

Exercise 14.2 Show that the following languages are not in \mathbf{Regular} by constructing an infinite fooling set.

  1. \{\textcolor{darkred}{\mathtt{0}}^{2n}\textcolor{darkred}{\mathtt{1}}^n:n\in \mathbb{N}\}.
  2. \{w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^*:|w|_{\textcolor{darkred}{\mathtt{0}}}=2|w|_{\textcolor{darkred}{\mathtt{1}}}\}.
  3. The language of all words fo the form w_1\textcolor{darkred}{\mathtt{\#}}w_2\textcolor{darkred}{\mathtt{\#}}\cdots\textcolor{darkred}{\mathtt{\#}}w_n where each subword w_i is in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* and there exists w_i=w_j for some i\neq j.
  4. \{\textcolor{darkred}{\mathtt{0}}^{n^2} :n\in \mathbb{N}\}.
  5. \{\textcolor{darkred}{\mathtt{0}}^{2^n} :n\in \mathbb{N}\}.
  6. \{\textcolor{darkred}{\mathtt{0}}^{F_n} :n\in \mathbb{N}\}, where F_n is the nth Fibonacci number.
  7. (🔥) \{\textcolor{darkred}{\mathtt{0}}^{p_n} :n\in \mathbb{N}\}, where p_n is the nth prime number.
  8. (🔥) \{w\in \textcolor{darkred}{\mathtt{1}}\{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\exists n\in \mathbb{N}\ \mathsf{value}_{2}(w)=n^2\}, where \mathsf{value}_{2}(w) is the natural number whose binary representation is w.

14.2 Non-regularity via closure properties

Closure properties can be used to show that a language L is not in \mathbf{Regular}, by reducing this to the known fact that another (usually simpler) language L' is not in \mathbf{Regular}. This is essentially using the contrapositive of the closure properties.

Example 14.4 For example, \mathbf{Regular} being closed intersection means that if L_1 and L_2 are in \mathbf{Regular} then L_1\cap L_2 is in \mathbf{Regular} too. Which, taking the contrapositive, can be equivalently stated as:

If L_1\cap L_2\notin \mathbf{Regular} then either L_2\notin \mathbf{Regular} or L_2\notin\mathbf{Regular}.

This immediately gives that \{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|_{\textcolor{darkred}{\mathtt{a}}}=|w|_{\textcolor{darkred}{\mathtt{b}}}\}\notin \mathbf{Regular}.

\{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}=\{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|_{\textcolor{darkred}{\mathtt{a}}}=|w|_{\textcolor{darkred}{\mathtt{b}}}\}\cap \mathscr{L}(\textcolor{darkred}{\mathtt{a}}^*\textcolor{darkred}{\mathtt{b}}^*)\ . Since \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}\notin\mathbf{Regular} (as we saw in Example 14.1), then either \{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|_{\textcolor{darkred}{\mathtt{a}}}=|w|_{\textcolor{darkred}{\mathtt{b}}}\}\notin\mathbf{Regular} or \mathscr{L}(\textcolor{darkred}{\mathtt{a}}^*\textcolor{darkred}{\mathtt{b}}^*)\notin\mathbf{Regular}. But clearly \mathscr{L}(\textcolor{darkred}{\mathtt{a}}^*\textcolor{darkred}{\mathtt{b}}^*)\in \mathbf{Regular}, therefore \{w\in \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* :|w|_{\textcolor{darkred}{\mathtt{a}}}=|w|_{\textcolor{darkred}{\mathtt{b}}}\}\notin\mathbf{Regular}.

Caution

If you are not absolutely sure of what you are doing, always use closure properties in the forward direction. That is, establish that L and L' are regular, then conclude that L \circ L' must be regular (for some operation \circ).

Exercise 14.3 Only using that \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}\notin\mathbf{Regular} and the closure properties of \mathbf{Regular} show that the following languages are also not in \mathbf{Regular}:

  1. (🌱) \{\textcolor{darkred}{\mathtt{0}}^n\textcolor{darkred}{\mathtt{1}}^n :n\in \mathbb{N}\}

  2. \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^m :n,m\in \mathbb{N} \land n\neq m\}

  3. \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N} \land n\geq 1\}

  4. \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n\textcolor{darkred}{\mathtt{c}}^n :n\in \mathbb{N}\}

  5. \{\textcolor{darkred}{\mathtt{a}}^{2n}\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}

  6. \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^m :\text{if }n \text{ is odd then } n=m\}

  7. \{w\in \{\textcolor{darkred}{\mathtt{0}},\textcolor{darkred}{\mathtt{1}}\}^* :\exists n\in \mathbb{N}\text{ s.t. }\mathsf{value}_{2}(w)=2^n(2^n-1)\}

  8. (🔥) C++ (the programming language)

    Focus on very simple C++ programs with the same number of open { and }.

    The programs of the form int main (){}, int main (){{}}, int main (){{{}}}, …

Exercise 14.4 (🔥🔥) Can we prove using only \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}\notin\mathbf{Regular} and the closure properties of \mathbf{Regular} that every non-regular language L\subseteq \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* is indeed non-regular?

Compare the cardinality of the non-regular languages L\subseteq \{\textcolor{darkred}{\mathtt{a}},\textcolor{darkred}{\mathtt{b}}\}^* vs the cardinality of the languages that you can describe using closure properties of \mathbf{Regular}, languages in \mathbf{Regular} and \{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb{N}\}.

14.3 Non-regularity via Pumping Lemma

Another way to prove that a given language is non-regular is the Pumping Lemma. Theorem 14.1 relied on the pigeonhole principle to show that a language is non-regular. The Pumping Lemma below also relies on the pigeonhole principle but used in a different way.

Lemma 14.1 (Pumping Lemma for regular languages) Let L\subseteq \Sigma^*. If for every p\in \mathbb{N}, there exist a word w\in\Sigma^* s.t.

  • |w|\geq p,
  • w\in L, and
  • for every x,y,z\in \Sigma^* s.t. w=xyz, y\neq \varepsilon and |xy|\leq p there exist k\in \mathbb{N} s.t. xy^kz\notin L,

then L\notin\mathbf{Regular}.

Suppose, towards a contradiction, that L\in \mathbf{Regular}. Then by Definition 13.1 and Theorem 13.1, there must exist a DFA A=(Q,\Sigma,\{q_0\},F,\delta) s.t. \mathscr{L}(A)=L.

We want to show that the hypothesis of the lemma must be false, that is we want to show that

there exists a p\in \mathbb N s.t. for every word w\in\Sigma^*, if |w|\geq p and w\in L, then there exist x,y,z\in \Sigma^* s.t. w=xyz, y\neq \varepsilon, |xy|\leq p and for every k\in \mathbb{N} xy^kz\in L.

Let p=|Q| and w be an arbitrary word s.t. w\in L and |w|=n\geq p. Let w[i] be the i-th symbol of w (we start counting from 1) and w[i:j] (with i\leq j) be the concatenation of the symbols of w between positions i and j included.

Since w\in L, there must exist a sequence of states q_0,q_1,\dots,q_n\in Q s.t. q_n\in F and for each i\in \{0,1,\dots,n-1\}, \delta(q_i,w[i])=q_{i+1}. The tuple of states q_0,\dots,q_n has size n+1>p=|Q|, hence by the pigeonhole principle (see Section 2.2.1), the states q_0,\dots,q_n cannot be all distinct. Let \ell be the first index in the sequence s.t. exists i<\ell with q_i=q_\ell.

Let x=w[1:i] (if i=0 take x=\varepsilon), y=w[i+1:\ell], and z=w[\ell+1:n]. See Figure 14.1 for a visual depiction of the paths giving x,y,z.

Figure 14.1

The states from q_0,\dots,q_{\ell-1} must be all distinct, by the choice of \ell. Hence \ell\leq |Q|=p and |xy|=\ell\leq p. It is also immediate to see that y\neq \varepsilon.

To conclude we need to show that for every k\in \mathbb N, xy^k z\in L. It is immediate to construct a path accepting the word xy^kz: take the original path but repeat the cycle between the q_i and q_\ell k-times.

The Pumping Lemma is essentially saying that we can win the following game. Given a language L we want to prove is not regular:

  • the “adversary” picks p\in \mathbb N (p is usually called the pumping length);
  • we choose a word w\in L with |w|\geq p (as a function of p);
  • the adversary chooses x,y,z s.t.
    • w=xyz
    • |xy|\leq p
    • y\neq \varepsilon
  • we choose k\in \mathbb N (as a function of n,x,y,z)
  • if we prove that xy^kz\notin L we win (i.e. we proved L is not a regular language).

Hence a “template” for a proof using the pumping lemma for regular languages is as follow:

We prove that L is non-regular using the pumping lemma. Let p be the pumping length. Consider the word w=..... We have that |w|\geq p and w\in L (this needs an argument, possibly trivial, but you need to check it). Given a decomposition of w as w=xyz, with |xy|\leq p and y\neq \varepsilon, consider the natural number k=..... To conclude we need to prove that xy^kz\notin L (this needs an argument, usually quite non-trivial).

Example 14.5 Following the template, above we show (again) that L=\{\textcolor{darkred}{\mathtt{a}}^n\textcolor{darkred}{\mathtt{b}}^n :n\in \mathbb N\}\notin \mathbf{Regular}\ . We already saw a proof of this fact in Example 14.1 using a fooling set.

We prove that L is non-regular using the pumping lemma. Let p be the pumping length. Consider the word w=\textcolor{darkred}{\mathtt{a}}^p\textcolor{darkred}{\mathtt{b}}^p. We have that |w|\geq p and clearly w\in L. Given a decomposition of w as w=xyz, with |xy|\leq p and y\neq \varepsilon, consider the natural number k=0. To conclude we need to prove that xy^kz\notin L. Since |xy|\leq p it must be that x=\textcolor{darkred}{\mathtt{a}}^i, y=\textcolor{darkred}{\mathtt{a}}^j and z=\textcolor{darkred}{\mathtt{a}}^{p-i-j}\textcolor{darkred}{\mathtt{b}}^p. Since y\neq \varepsilon, then j> 0. The word xy^kz=\textcolor{darkred}{\mathtt{a}}^{p+j(k-1)}\textcolor{darkred}{\mathtt{b}}^p=\textcolor{darkred}{\mathtt{a}}^{p-j}\textcolor{darkred}{\mathtt{b}}^p. Since j>0, then p-j\neq p and xy^0z\notin L.

WarningCommon errors

To avoid errors in the use of the Pumping Lemma stick to the proof template. The creative part is in the choice of the orange parts not in the structure of the argument.

  • We cannot use the Pumping Lemma to show that a language L\in \mathbf{Regular}. The Pumping Lemma is not an if and only if.
  • The word w must depend on p. If our choice of w does not depend on p then it is wrong.
  • The word w cannot depend on x,y,z. If our choice of w does depend on x,y,z then it is wrong.
  • The word w does not need to have length exactly p, it might be much much larger, for example p!.
  • Another common error is to choose x,y,z. We cannot choose them! The only things we know about them is that w=xyz, |xy|\leq p and y\neq\varepsilon. The adversary chooses x,y,z with the given constraints, not us.
  • Another common error is to assume x\neq\varepsilon! It might be that x=\varepsilon, the part we know it is non-empty is y!
  • Choosing k=1 will never work. Often k=0 is a good choice but not always. Remember that k doesn’t need to be a fixed constant, it might depend on p and x,y,z.

Exercise 14.5 Prove again that the languages in Exercise 14.3 are non-regular but now using the Pumping Lemma (and possibly some closure property of regular languages).