## 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  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 where  for i ≥ 1. We now see that no two of these are equivalent to each other with respect to ${\mathbf{\equiv }}_{\mathbf{A}}$.

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.

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