Let ||L|| be the sum of all lengths of words in L und N(L) the number of equivalence claesses for the Relation $\equiv_L$ from Myhill–Nerode theorem. Proof, which values d can have with $d:=||L||-N(L),d\in\mathbb{Z}$

Some conclusions I came up with so far:

  • |L|| is infinite, when L is infinite. Then d is not defined.
  • When N(L) is infinite for any non regular language, so L is infinite as well and $\infty - \infty $ wouldn´t be defined.
  • So say ||L|| is finite then N(L) is finite as well because every word hase to be in a certain class. If not ||L|| would be infinite. Though when N(L) is finite, ||L|| doesn´t have to be finite since we might have some symbols looping over states.
  • d is probably never negative, because if N(L) > ||L|| we would have classes which don´t belong to words in L.
  • When d = 0 then, N(L) = ||L|| and there would be a class for every word in L.

So d can be anything from $\{ 0,...,\infty \}$

Might this be enough for an answer or am I missing any cases/details? Where could I be proofing more formally?


1 Answer 1


In order to make the question nontrivial, you have to assume that $L$ is finite. You haven't specified what the alphabet is, so I will assume that the alphabet is arbitrary.

First, let us show that $N(L) \leq \|L\|+2$. We can construct a DFA for $L$ whose states consist of all prefixes of words in $L$, together with a failure state. This DFA contains an initial state (corresponding to the empty prefix), a failure state, and one state for every non-empty prefix. In particular, $$ N(L) \leq 2 + \sum_{w \in L} |w| = 2 + \|L\|. $$ In other words, $d \geq -2$.

Second, let us consider the language $L_\Sigma = \{\sigma : \sigma \in \Sigma\}$ over an alphabet $\Sigma$. The minimal DFA for this language contains three states, and so the value of $d$ for $L_\Sigma$ is $$ \|L_\Sigma\| - N(L_\Sigma) = |\Sigma| - 3. $$ As $\Sigma$ ranges over all possible alphabets, we obtain all values which are at least $-2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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