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 x L y in this case.  (Here L is an equivalence relation).

 

Example:

 

It is not a regular language. 

 

Solution:

 

Consider the sequence of strings x1, x2 .......where xi = 0i for i ≥ 1. We now see that no two of these are equivalent to each other with respect to A.

 

Consider xi = 0i and xi = 0j for i ≠ j

 

Let z = 1i and notice that xi z = 0i 1j A but  xi z = 0j 1i A.

 

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

 

Theorem:

 

A certain language L1 is regular if and only if it has a finite number of equivalences classes. Moreover, there is a DFA M with L(M) = L1 having precisely one state for each equivalence classof 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.