This is an ode (although it is not a poem) to the Myhill-Nerode Theorem, thank God for it.

I saw a question that required one to show that the language of strings of EVEN length is regular. Formally, it means to show that
$EVEN = \{ w | |w| = 2n, n \in \mathbb{N} \}$ is regular.

The way people have approached this is to specify an alphabet like $\{0,1 \}$ and then construct a NFA or a DFA (finite automaton) that recognises only a even strings from these alphabets. A sample is found below

NFA of Even length

Hmmm, I am uncomfortable with this. Why? We have not been given any alphabet information on the problem. Why use or limit it to $\{0,1 \}$? What if the alphabet is composed of $\{a,b,c \}$, are we not capable of producing strings of even length from this alphabet? Sure we can but what happens to our DFA proof? It will fall short. I feel it is not a good approach, and I do not think it is rigorous, even though the proof is concisely crisp. The proof should handle the generic case with no appeal as to how the alphabet looks like. I believe that is the best approach. We can of course handle the general case by stating a general assumption on $\Sigma$ and say $\Sigma = \{ a_1, a_2,a_3,...,a_n \}$. Then we replace the 0/1 notation in the diagram with $a_1/a_2/a_3/.../a_n$., then we are done. That covers every possibility and will only accept a string of even length.

Anyway back to the problem what if we have not been given the composition of  $\Sigma$ ?

The Myhill-Nerode Theorem ( briefly treated here) if we know it is there to rescue you. Briefly it effectively states that the following statements are equivalent:

• $L \subseteq \Sigma^*$ is regular
• The relation $R_L$, such that $x,y \in \Sigma^*, (x,y) \in R_L$ iff $\forall z \in \Sigma^*, xz \in L$ exactly when $yz \in L$, is finite.

We prove now that $EVEN$ is regular:
Proof:

Form the membership $R_L$ iff the right side is satisfied. Hence, $(x,y) \in R_L$ then we have two cases for $z$.
1. $z$ may be of even length $m$. Then $xz \in EVEN$, because $|xz| = |x|+|z| = 2n + m$ is even because an even number ($2n$) + even number($m$) results an even number, thus $xz \in EVEN$. Similarly for $yz \in EVEN$, the same argument applies.
2. $z$ may be of odd length $m$. Then $xz \not \in EVEN$, because $|xz| = |x|+|z| = 2n + m$ is odd because an even number ($2n$) + odd number($m$) results an odd number, thus $xz \not \in EVEN$. Similarly for $yz \not \in EVEN$, the same argument applies.
3. There is only one equivalence class we can make of $R_L$, so finite.

We have shown that the second part of the above theorem is satisfied by our $EVEN$ language, and since by the theorem, this is equivalent to the first part, we then conclude that $EVEN$ is regular.

Q.E.D.

LPC