Article #215
Subject: Reply to Mr. Cruz's Question
Author: Andrew W. Harrell
Posted: 11/7/2013 03:55:19 PM

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

Article #216
Subject: my response
Author: Andrew W. Harrell
Posted: 11/7/2013 03:56:09 PM

Dr. Andrew W. Harrell permalink



November 8, 2013 5:31 am



Please Note: Your comment is awaiting moderation.



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.