The Myhill-Nerode theorem is used to prove that a certain language is regular or not.
It can be also used to find the minimal number of states in a Deterministic Finite Automata (DFA).
Let L be any language over Σ*. Consider strings x, y ∊ Σ* are indistinguishable by L if and only if for every string z ∊ Σ* either both xz and yz are in L or both xz and yz are not in L.
We can write in this case. (Here is an equivalence relation).
It is not a regular language.
Consider the sequence of strings where for i ≥ 1. We now see that no two of these are equivalent to each other with respect to .
Consider and for i ≠ j.
Let and notice that but .
Therefore no two of these strings are equivalent to each other and thus given language L cannot be regular.
A certain language is regular if and only if it has a finite number of equivalences classes. Moreover, there is a DFA M with having precisely one state for each equivalence classof .
Q. Consider a language
By which theorem we can prove given language is regular or not.
(a) Ogdem’s Theorem
(b) Pumping Lemma
(c) Myhill-Nerode theorem
(d) Rice Theorem
Answer: Option (c)
Myhill-Nerode theorem is used to prove a certain language is regular or not.
Note: Pumping Lemma is only used to prove a certain language is not regular.