Proof for values of d with d:= ||L|| - N(L) with $d in mathbb{Z}$ and N(L) Nerode Index

Question

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),dinmathbb{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?

Yuval Filmus · Answer

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

Proof for values of d with d:= ||L|| - N(L) with $d in mathbb{Z}$ and N(L) Nerode Index

One Answer

Add your own answers!

Ask a Question