A Myhill-Nerode type characterization of the regular languages using fooling sets?
Your conjecture is refuted by the language $\{ 0^n : \text{$n$ is not a power of $2$}\}$. Let $\{(x_i,y_i) : i \in \mathbb{N}\}$ be an infinite fooling set for this language. We can identify $x_i,y_i$ with integers. These pairs have to satisfy the following conditions:


$x_i + y_i$ is not a power of $2$.
For each $i \neq j$, either $x_i + y_j$ is a power of $2$ or $x_j + y_i$ is a power of $2$.


Color $\mathbb{N}^2$ with two colors according to whether $x_i + y_j$ is a power of $2$ or $x_j + y_i$ is a power of $2$, where $i &lt; j$. Ramsey's theorem shows that without loss of generality we can assume that for all $i &lt; j$, $x_i + y_j$ is a power of $2$.

If $x_i = x_j$ for $i &lt; j$ then $x_j + y_j$ is a power of $2$, contradicting (1) above. Similarly, if $y_i = y_j$ for $i &lt; j$ then $x_i + y_i$ is a power of $2$, contradicting (1) above. Thus all $x_i$ are distinct and all $y_j$ are distinct.

Assume without loss of generality that $x_1 &lt; x_2$. Let $x_1 + y_3 = 2^a$ and $x_2 + y_3 = 2^b$. Choose $j$ so that $y_j &gt; 2^b$. Let $x_1 + y_j = 2^c$. Then $2^c &lt; x_2 + y_j &lt; 2^c + 2^b &lt; 2^{c+1}$, and we obtain a contradiction.