Proof for the amount of states of a regular language

Question

Let L be a formal language. Two words $u,v \in \Sigma^*$ are called separable if $\exists w \in \Sigma^* : uw \in L, vw \not\in L$.

Nerode lemma: Let L be a formal language. If there are $n$ words of L that are pairwise separable, a final state machine that recognizes L would have at least $n$ states.

Let $L_i = \{ubv \; | \; u,v \in \{a,b\}^*, |v| = i - 1\}$. I now need to prove that a final state machine for $L_i$ contains at least $2^i$ states using the defintion and lemma above. Therefore there should be $2^i$ pairwise separable words.

I tried this for $L_2$:

"-" means that the two words are not separable. The fields marked with "x" are ignored because of the symmetry. Therefore e.g. $\lambda$ and $b$ are separable by $a$ because $\lambda.a = a \not\in L \wedge b.a \in L$. Nevertheless instead of 4 pairwise separable items ($2^2$) I only got three: $\lambda,a$ and $ba$. One is missing.

Could you please help me to find the missing one and a possibility to prove it for all $L_i$?

Thanks in advance!

Answer 1

Let $E = \Sigma^i$. Clearly $|E| = 2^i$. I claim that all pairs from $E$ are separable.

Suppose $u,v \in E$, with $u \neq v$. Let $k$ be the last index such that $[u]_k \neq [v]_k$. WLOG, we can take $[u]_k = b$. Then $u$ has the form $u = \alpha b \beta$, with $|\alpha| = k-1$, $|\beta| = i-k$. Choose $w = a^{k-1}$ (possibly empty).

Then we have $[uw]_{|uw|-i+1} = b$, but $[vw]_{|vw|-i+1} = a$, so we have that $uw \in L_i$, but $vw \notin L_i$.

Answer 2

For my own benefit I made a somewhat more complete table showing what words of length at most $1$ separate $\lambda,a,b,ab,ba$, and $bb$:

$$\begin{array}{c|cc} &\lambda&a&b&ab&ba&bb\\ \hline \lambda&-&-&a,b&a,b&\lambda&\lambda,a,b\\ a&-&-&a,b&a,b&\lambda&\lambda,a,b\\ b&a,b&a,b&-&-&\lambda,a,b&\lambda\\ ab&a,b&a,b&-&-&\lambda,a,b&\lambda\\ ba&\lambda&\lambda&\lambda,a,b&\lambda,a,b&-&a,b\\ bb&\lambda,a,b&\lambda,a,b&\lambda&\lambda&a,b&- \end{array}$$

It’s clear that any pairwise separable set can contain only one of $\lambda$ and $a$ and only one of $b$ and $ab$, but we still have four pairwise separable sets of cardinality $4$ here, $\{\lambda,b,ba,bb\}$, $\{\lambda,ab,ba,bb\}$, $\{a,b,ba,bb\}$, and $\{a,ab,ba,bb\}$; the trick is to find one that generalizes.

The one with the most regular structure seems to be $\{a,b,ba,bb\}$, which factors as $\{\lambda,b\}\{a,b\}$. This suggests that the set $\{\lambda,b\}\{a,b\}^{i-1}$ might be pairwise separable relative to $L_i$. Indeed, if you happen to notice that $a$ and $a^2$ behave identically with respect to separation, as do $b$ and $ab$, you could even note that $\{aa,ab,ba,bb\}$ is pairwise separable and try $\{a,b\}^i$.

Suppose that $u,v\in\{a,b\}^i$. If $u=u_1ba^j$, $v=v_1ba^k$, and $j<k$, it’s easy to separate $u$ and $v$: if $w$ is any word of length $i-k-1$, $uw\notin L_i$, but $vw\in L_i$. Thus, it only remains to separate $u$ and $v$ when $j=k$. Assuming that $u\ne v$, we can without loss of generality write $u_1=u_2au_3$ and $v_1=v_2bu_3$, so that $u=u_2au_3ba^j$ and $v=v_2bu_3ba^j$. Then $u$ and $v$ are separated by any word $w$ of length $i-(j+|u_3|)$: $vw\in L_i$, but $uw\notin L_i$.