Scribd
Upload
501 views

Myhill Nerode Theorem

The Myhill-Nerode theorem provides a method to determine if a language is regular and to minimize the number of states in a deterministic finite automaton (DFA) that recognizes the language. It states that a language is regular if its equivalence classes have a finite number. The equivalence classes are based on strings having no distinguishing extensions. The theorem can be used to minimize a DFA by merging states that cannot be distinguished based on remaining input. An example is provided to demonstrate minimizing a 6-state DFA to a 3-state DFA using the Myhill-Nerode theorem.

Uploaded by

Samridhi Shree
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
501 views

Myhill Nerode Theorem

The Myhill-Nerode theorem provides a method to determine if a language is regular and to minimize the number of states in a deterministic finite automaton (DFA) that recognizes the language. It states that a language is regular if its equivalence classes have a finite number. The equivalence classes are based on strings having no distinguishing extensions. The theorem can be used to minimize a DFA by merging states that cannot be distinguished based on remaining input. An example is provided to demonstrate minimizing a 6-state DFA to a 3-state DFA using the Myhill-Nerode theorem.

Uploaded by

Samridhi Shree
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Myhill Nerode Theorem

The Myhill Nerode theorem is a fundamental result coming down to the theory of languages.
This theory was proven by John Myhill and Anil Nerode in 1958. It is used to prove whether
or not a language L is regular and it is also used for minimization of states in
DFA( Deterministic Finite Automata).

Statement of Myhill Nerode Theorem


This theorem states that a language L is regular if and only if L~ has a finite number of equivalence
classes. Furthermore, if this finite number of equivalence classes is N, then N is the number of states in
minimal DFA (Deterministic Finite Automaton) recognizing L.
Here L~ is a relation on strings x, y such that there is no distinguishing extension for x and y.
To understand the above statement, we need to understand what is meant by distinguishing extension.
For a language L and a pair of strings x and y, a distinguishing extension is a string z such that exactly
one of the two strings xz and yz belongs to L.

Proof of Myhill Nerode Theorem


Suppose L is a regular language
By definition, there is a DFA (say A) that recognizes it with finitely many states (say n)
Let’s divide the set of all finite strings into ‘n’ subsets - S 1, S2 ……. SN, such that when Si is given as
input to automaton A, it makes it to end in state i.
Next, for every two strings x and y belonging to the same subset Si, automaton A reaches the same state
on input xz and yz for any choice of third string z, and therefore A must accept both xz and yz or reject
both of them.
Thus, not any string z can be a distinguishing extension for x and y, so they must be related by L~.

Example of Myhill-Nerode

Minimization of DFA with Myhill-Nerode theorem.

Follow these steps to achieve this:


1. Make a table for each pair of states.
In the above example, there are six states, A, B, C, D, E, F. So we'll make the table row-wise and column-
wise because we have to make the pairs. But we'll cut the table diagonally because the pairs are repeated
twice, so we'll discard the upper part.

2. Mark all the pairs while P દ F and Q∉F.


Now we'll mark the pairs where P is a final state and Q is a non-final state. So in the pair, BA both are
non-final states. So we'll not mark that pair. Next is the CA pair. In this, the C is a final state, then we'll
mark this pair, and this process goes on for all the pairs. So we have to mark the pair whenever there is
one final state, and the other is non-final.

3. Mark the (P, Q) state if any unmarked state pairs exist δ(P,x),δ(Q,x) is marked. Continue until
no more markings are possible.
Firstly, we'll check the unmarked pairs. So the first pair is the BA. We'll do the δ of BA with 0 first and
then with 1.
δ(B,0)=A , δ (A,0)=B , So here the pair is AB. Now check whether this pair is marked or not. If it is not
marked, then we'll move further. Now check for
δ(B,1)=D , δ (A,1)=C. Now check whether the DC pair is marked or not. We'll forward the next pair if it
is not marked. We'll repeat this process with all the unmarked pairs, and if any pair after the transition is
marked, then we have to mark that pair on which the transition is being done.
In the above example, it is with the FA and FB pair because after transition, it is marked, so we have to
mark the FA and FB pair also.

4. Make a single state in the minimized DFA by combining all the unmarked pairings.
First, we'll take the unmarked pairs, which are (AB),(DC), (ED), and (EF). Now let's combine the
unmarked pairs.

Now here we'll make the AB pair as a single state, and the other three pairs are connected with each. So
instead of making three different states will make it as one state and add the remaining F in the DFA, this
will be how we'll minimize the DFA.
This is the minimized DFA having 3 states, whereas the Original DFA was having three states.

You might also like