Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$:

enter image description here

"-" 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!

share|cite|improve this question
Related:… – Ted May 31 '12 at 2:21
up vote 3 down vote accepted

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$.

share|cite|improve this answer

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.