CREATE OWN LIBRARY

Myhill-Nerode Theorem

Application:

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).

Definition:

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 $\mathbf{x}\mathbf{ }{\mathbf{\equiv }}_{\mathbf{L}}\mathbf{ }\mathbf{y}$ in this case.  (Here ${\mathbf{\equiv }}_{\mathbf{L}}$ is an equivalence relation).

Example:

It is not a regular language. 

Solution:

Consider the sequence of strings ${\mathbf{x}}_{\mathbf{1}}\mathbf{,}\mathbf{ }{\mathbf{x}}_{\mathbf{2}\mathbf{ }\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}\mathbf{.}}$where ${\mathbf{x}}_{\mathbf{i}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{0}}^{\mathbf{i}}$ for i ≥ 1. We now see that no two of these are equivalent to each other with respect to ${\mathbf{\equiv }}_{\mathbf{A}}$.

Consider ${\mathbf{x}}_{\mathbf{i}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{0}}^{\mathbf{i}}$ and ${\mathbf{x}}_{\mathbf{i}}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{0}}^{\mathbf{j}}$ for i ≠ j. 

Let $\mathbf{z}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{1}}^{\mathbf{i}}$ and notice that ${\mathbf{x}}_{\mathbf{i}}\mathbf{ }\mathbf{z}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{0}}^{\mathbf{i}}\mathbf{ }{\mathbf{1}}^{\mathbf{j}}\mathbf{ }\mathbf{\notin }\mathbf{A}$ but  ${\mathbf{x}}_{\mathbf{i}}\mathbf{ }\mathbf{z}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{0}}^{\mathbf{j}}\mathbf{ }{\mathbf{1}}^{\mathbf{i}}\mathbf{ }\mathbf{\in }\mathbf{A}$.

Therefore no two of these strings are equivalent to each other and thus given language L cannot be regular.

Theorem:

A certain language ${\mathbf{L}}_{\mathbf{1}}$ is regular if and only if it has a finite number of equivalences classes. Moreover, there is a DFA M with $\mathbf{L}\mathbf{\left(}\mathbf{M}\mathbf{\right)}\mathbf{ }\mathbf{=}\mathbf{ }{\mathbf{L}}_{\mathbf{1}}$ having precisely one state for each equivalence classof ${\mathbf{\equiv }}_{\mathbf{A}}$.

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)

Explanation:

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.