Do you think IIT Guwahati certified course can help you in your career?
Introduction
The Myhill Nerode Theorem is one of the fundamental theorems of the Theory of Computation, proven by Anil Nerode and John Myhill in 1958. This theorem is used to prove whether a language is regular or not. It can also be used to minimize states in Deterministic Finite Automata (DFA).
What is the Myhill–Nerode theorem?
The Myhill–Nerode theorem is a fundamental result in formal language theory that provides a characterization of regular languages. It states that a language is regular if and only if it has a finite number of equivalence classes under the Myhill–Nerode relation. This theorem helps in minimizing finite automata and proving whether a language is regular or not.
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, and 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 - S1, S2 ……. SN, such that when Si is given as input to automaton A, it makes it end in state i.
Next, for every two strings x and y belonging to the same subset Si, an 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, no string z can be a distinguishing extension for x and y, so they must be related by L~.
Example of Myhill-Nerode
Let's look into the example of the Myhill-nerode Theorem.
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.
Use and Consequences of Myhill-Nerode Theorem in TOC
This theorem states that a language L is regular if and only if L~ has a finite number of equivalence classes. 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.
Applications of Myhill-Nerode theorem
Minimization of Finite Automata – The theorem helps in constructing the smallest possible deterministic finite automaton (DFA) for a given regular language by identifying equivalent states.
Regular Language Identification – This provides a method to prove whether a language is regular or not by checking if the number of equivalence classes is finite.
Grammar and Compiler Design – Used in lexical analysis and syntax parsing to optimize token recognition and improve compiler efficiency.
Complexity Analysis of Languages – Helps in studying the structural complexity of formal languages by determining the number of distinct equivalence classes.
Automata Theory and Theoretical Computer Science – Used in formal verification, algorithm design, and decision problems related to regular languages.
Frequently Asked Questions
What is the Myhill–Nerode theorem to prove regularity?
The Myhill–Nerode theorem proves regularity by checking if a language has a finite number of equivalence classes under the Myhill–Nerode relation, ensuring it is regular.
What is the use of the Myhill–Nerode theorem?
The theorem is used for minimizing DFAs, proving language regularity, optimizing lexical analysis, and analyzing the structural complexity of formal languages in automata theory.
What does the Myhill-Nerode theorem state?
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 recognizing L.
How do you minimize DFA with the Myhill-Nerode theorem?
Follow these steps to minimize DFA with the Myhill-Nerode theorem:
Make a table for each pair of states.
Mark all the pairs while Pદ F and Q∉F.
Mark the (P, Q) state if any unmarked state pairs exist δ(P,x),δ(Q,x) is marked. Continue until no more markings are possible.
Make a single state in the minimized DFA by combining all the unmarked pairings.
What is the difference between the pumping lemma and the Myhill-Nerode Theorem?
The pumping lemma and Myhill-Nerode Theorem are both used in formal language theory. The pumping lemma asserts properties of regular languages, while Myhill-Nerode provides a criterion for decidability of regularity based on equivalence classes of strings.
What is Myhill-Nerode theorem automata?
According to the Myhill-Nerode Theorem, the number of states in the smallest automaton that accepts L equals the number of equivalence classes in RL. In the Myhill-Nerode Theorem, a language L is regular if and only if the number of RL equivalence classes is finite.
Conclusion
This article discussed the ‘My-hill Nerode Theorem’ - one of the basic theorems in the Theory of Computation (TOC) in detail.
39+ registered 
