Skip to content

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

November 2, 2013

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

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

Advertisements
2 Comments leave one →
  1. November 8, 2013 5:31 am

    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.

    • November 8, 2013 10:02 am

      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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: