If you want to make money online : Register now

[Solved]: Basic Myhill-Nerode Theorem Practice

, , No Comments
Problem Detail: 

I wanted to understand the Myhill-Nerode Theorem so I made up a small example to do so.

L = (a $+$ b )

Clearly, this language is regular. So, I should be able to establish a finite number of equivalence classes by using this method.

I start with a suffix of length 0, which is only $\lambda$:

a$\lambda$ = a $\in$ L
b$\lambda$ = b $\in$ L

For all suffix strings of length $\nu \gt 0$, both are not elements of L. Therefore, there are no distinguishable strings. I suspect this means there are 0 equivalence classes, and since 0 is a finite number, the language is regular. What might be missing from this analysis?

Note: I made sure to do some online research already and feel comfortable with the ideas of distinguishable strings. The equivalence class bit is what I probably need some clarification on.

Asked By : Dr Quest

Answered By : Yuval Filmus

What you show is that $a$ and $b$ belong to the same equivalence class. Indeed, in this case there are exactly three equivalence classes: $\{\lambda\}$, $\{a,b\}$, and $\{ w : |w| \geq 2 \}$ (that's assuming the alphabet is $\{a,b\}$). I'll leave it as an exercise to prove that.

The Myhill–Nerode equivalence classes are intimately related to the minimal DFA. Indeed, given the minimal DFA, the number of equivalence classes equals the number of states, and each equivalence class consists of all strings which end up at that state. That's the quickest way to find the equivalence classes in simple cases such as $a+b$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48340

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback