# An ode to the Myhill-Nerode Theorem or how to show a language is regular without DFAs

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

is regular.

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

Hmmm, I am uncomfortable with this. Why? We have not been given any alphabet information on the problem. Why use or limit it to ? What if the alphabet is composed of , 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 and say . Then we replace the 0/1 notation in the diagram with ., 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 ?

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:

- is regular
- The relation , such that iff exactly when , is finite.

We prove now that is regular:

**Proof**:

Form the membership iff the right side is satisfied. Hence, then we have two cases for .

1. may be of even length . Then , because is even because an even number () + even number() results an even number, thus . Similarly for , the same argument applies.

2. may be of odd length . Then , because is odd because an even number () + odd number() results an odd number, thus . Similarly for , the same argument applies.

3. There is only one equivalence class we can make of , so finite.

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

Q.E.D.

LPC

Hello again Mr. Cruz. You asked, “But, what happens to your[our proof] if we have an alphabet a,b,c and not just of 0’s and 1’s”. But, according to my friend Dr. Ullman’s book Intro to Automata Theory and Languages, these types of FA machines {called Mealy) are equivalent to the Moore ones. Is he wrong? What do you say? We can discuss it at length, over a long period of time, on my website’s discussion board if you like.

Hi Dr. Harell,

I had a look at the Mealy and Moore machines and I observe that they just do not reply with either accept (i.e., ending in an accept state) or reject (i.e., ending in a reject state), but they output something also based on what is fed to them. I have not seen a proof of their equivalence which I am sure is in a book. However, just looking at the structure I got a feeling that they can be made to be equivalent.

LPC