Fooling Set

A fooling set is a set of strings where any two elements form a distinguishable pair, i.e. it is pair-wise distinguishable. Fooling sets provide a lower bound to the number of states a finite state automaton (FSA) requires to recognise a language.

Definition §

Fooling Set ^definition

Let $L$ be a language. Then a set of formulae, $F$, is a fooling set for $L$ iff:

$$\forall x\in L,\forall y\in L,\text{(x,y) is distinguishable in L}$$

• This is usually shortened to saying $F$ is a pairwise distinguishable set in $L$

Warning $F$ does not need to be in $L$!!!

Strategies For Constructing Fooling Sets §

1. Construct fooling set using prefixes of strings in $L$.

2. To construct ​$F_k$, consider strings for which it seems a counter that can count up to at least $k$ is needed to distinguish between them.

3. Often, it is possible to construct a fooling set​ $F_k$ such that for every string $x\in F_k$, there is a string $z$ such that $z$ distinguishes $x$ from the other strings in​ $F_k$, i.e. either $xz$ is in $L$ but $yz$ is not in $L$ for every other $y$ in $F_k$​, or vice versa.

Theorem §

T1: The fooling set for a language is a lower bound for the states of a DFA that recognises that language ^t1

Let $L$ be a language, and let $F$ be a fooling set for $L$ of size $k$ (i.e. $|F|=k$). Then:

$$\forall \text{DFA, D},\text{D recognises L}⟹\text{D has}\ge k\text{ states}$$

• $D$ = Some DFA that recognises $L$

Proof: proof by contradiction:

We can use a

• Let $M$ be a DFA that recognises $L$ having less than $k$ states, say $k-1$ states.
• Let $F$ be the fooling set for $L$ of size $k$
• Since we have more strings in $F$ than states in $M$, we will, by the pigeonhole principle, have at least one state which two strings have the same computation path to.
• This is the same as saying $q(x)=q(y)$ for some $x$ and $y$ in $F$. Here, $q(x)$ is notation for the extended transition function.
• By the memorylessness lemma, this means for every suffix string $z$, we have $q(xz)=q(yz)$
• But by the definition of a fooling set, $x$ and $y$ needs to be a distinguishable pair, and by a theorem relating it to DFAs, we must have $q(x)\ne q(y)$
• This leads to a contradiction

Hence, $M$ needs at least $k$ states.

C1: If the fooling set for a language is infinite, then the language is non-regular ^c1

This follows from the previous theorem. Let $L$ be a language and $F$ be a fooling set for $L$. Then:

$$\text{F is infinite}⟹\text{L is non-regular}$$

• Another way of saying that $F$ is infinite is saying that for every natural number $k$, there is a fooling set $F_k$ of size $k$. Mathematically, this is: $\forall k\in \mathbb{N},\exists F,|F|=k$

• Equivalently, $L$ has no finite state automaton that recognises it.

Proof:

This proof is very simple:

• If $F$ is infinite, then that means (by theorem 1) any DFA $D$ that recognises $L$ must have infinite states
• But a DFA is a finite state automata, so it cannot have finite states
• Therefore, no such DFA exists.
• Since a regular language requires a DFA to recognise it, if one does not exist, the language is non-regular.

C2: Myhill–Nerode Theorem ^c2

This is simply the contrapositive of the previous corollary. If a language is regular, then it must have a fooling set of finite length. Let $L$ be a language, and $F$ be a fooling set for $L$. Then:

$$\text{L is regular}⟹\text{F is finite}$$

Examples §

1: Simple Fooling Set

Construct a fooling set of size 3 for the given language below:

$$L=\{ϵ,1,10,100\}$$

Solution finite language, by just taking the elements of the language itself. However, to show that this is a fooling set, we need to find a distinguishable suffix for each pair of elements:

First off, note that we can always take the ‘trivial’ fooling set of a

• $(ϵ,1)$: We take $z=1$. Appending $ϵ\circ 1=1$, which is in $L$, while $1\circ 1=11$, which is not in $L$.
• $(ϵ,10)$: Again, just take $z=1$. Appending $ϵ\circ 1=1$, which is in $L$, while $10\circ 1=101$, which is not in $L$.
• $(1,10)$: Slightly harder, because the second string has the first string as a prefix. We can’t take $z=0$ because that would result in the pair $(10,100)$, both of which are in the language. Instead take $z=00$. This makes $1\circ 00=100$ which is in $L$, while $10\circ 00=1000$ which is not in $L$

Thus, we have taken every combination of pairs of elements and shown that each pair is a distinguishable pair, thus satisfying the definition of a fooling set.

So we have:

$$F_3=\{ϵ,1,10\}$$

being a fooling set of size 3 for $L$.

2: Fooling Set for a non-regular language ^e2

Find the infinite fooling set for the language below:

$$L=\{0^n{1}^n|n\ge 0\}=\{ϵ,01,0011,000111,\dots \}$$

Solution

We can start by finding a small fooling set, then looking at patterns to try to create a generalised, infinite version.

Take the fooling set $F_3=\{ϵ,0,00\}$:

• $(ϵ,0)$: We take $z=1$, $ϵ\circ 1=1\notin L$ while $0\circ 1=01\in L$
• $(ϵ,00)$: We take $z=11$, $ϵ\circ 11=11\notin L$ while $00\circ 11=0011\in L$
• $(0,00)$: Notice that the second string has the first string as a prefix. We can take $z=1$, $0\circ 1=01\in L$ but $00\circ 1=001\notin L$

If we draw this as a graph, we get a complete graph:

%%🖋 Edit in Excalidraw, and the dark exported image%%

The obvious next step would be to see if we can add another string of zero’s: $000$. If we do, the graph becomes:

%%🖋 Edit in Excalidraw, and the dark exported image%%

Notice that any pair just uses a distinguishing suffix consisting of $1$‘s. When we compair two pairs of zero’s, i.e. $(0^i,0^j)$ where $i<j$ then we take as many 1’s as the least number of zeroes:

• ($00$,$0000000$): This pair has $1^k$ as the distinguishing suffix, where $k$ is the smaller of the counts of zeroes. Here, we have $k=2$, so $1^2=11$ is the distinguishing suffix.
• The exception is when we compare a pair with $ϵ$, we take the larger count of zeroes. For example, $(ϵ,000)$ has the distinguishing suffix $z=111$

Then we can construct an infinite fooling set:

$$F_k=\{0^n|n\le k\}\forall k\in \mathbb{N}$$

#todo example for fooling set for language of palindromes.