What is Myhill–Nerode Theorem?

The answer to what is Myhill–Nerode Theorem:

John Myhill and Anil Nerode of the University of Chicago proposed a theorem in 1958 which provides a necessary and sufficient condition for a language to be regular. This theorem can also be used to minimize a DFA. But before going into the details of the theorem statement, we need to know some definitions related to the theorem.

Equivalence Relation

• A relation R in set S is Reflexive if xRx for every x in S.
• A relation R in set S is Symmetric if for x, y in S, yRx whenever xRy.
• A relation R in set S is Transitive if for x, y, and z in S, xRz whenever xRy and yRz.

A relation R in set S is called an equivalence relation if it is reflexive, symmetric, and transitive.

Right Invariant

An equivalence relation R on strings of symbols from some alphabet Σ is said to be right invariant if for all x, y ∈ Σ* with xRy and all w ∈ Σ* we have that xw R yw. This definition states that an equivalence relation has the right invariant property if two equivalent strings (x and y) that are in the language still are equivalent if a third string (w) is appended to the right of both of them.

Statement of the Myhill–Nerode Theorem

The Myhill–Nerode theorem states that the following three statements are equivalent.

1.     The set L, a subset of Σ*, is accepted by a DFA, i.e., L is a regular language.

2.     There is a right-invariant equivalence relation R of finite index such that L is the union of some of the equivalence classes of R.

3.     Let equivalence relation RL be defined as xRLy, if and only if for all z in Σ*, xz is in L exactly when yz is in L then RL is of finite index.

Myhill–Nerode Theorem in Minimizing a DFA

Step I: Build a two-dimensional matrix labeled by the states of the given DFA at the left and bottom sides. The major diagonal and the upper triangular parts are shown as dashes.

Step II: One of the three symbols, X, x, or 0 is put in the locations where there is no dash.

1.     Mark X at p, q in the lower triangular part such that p is the final state and Q is the non-final state.

2.     Make a distinguished pair combination of the non-final states. If there are n number of non-final states, there are nC2 number of distinguished pairs. Take a pair (p, q) and find (r, s), such that r = δ(p, a) and s = δ(q, a). If in the place of (r, s) there is X or x, in the place of (p, q), there will be x.

3.     If (r, s) is neither X nor x, then (p, q) is 0.

4.     Repeat (2) and (3) for final states also.

Step III: The combination of states where there is 0, they are the states of the minimized machine.

Consider the following examples to understand the discussed method. Click Here

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC
• What is Two-way infinite Turing machine?
• Example to generate Parse tree from the given grammar

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.