Myhill-Nerode Theorem

Astha
September 7, 2024

Abstract
The Myhill-Nerode theorem is a key concept in formal language theory that offers a deep
insight into regular languages. It states that a language is regular if and only if there is a finite
number of equivalence classes under a particular distinguishability relation. This result has broad
applications in computer science. It provides a clear method for proving a language’s regularity
by showing that the number of equivalence classes is finite. It also plays a crucial role in DFA
minimization by identifying and combining equivalent states, and can demonstrate when a language
is not regular by revealing an infinite number of equivalence classes. Moreover, the theorem forms
the basis for efficient DFA minimization algorithms, aids in formal verification and model checking
by simplifying state spaces, and helps differentiate regular languages from more complex ones.

1 Introduction
The Myhill-Nerode theorem is a key result in the theory of regular languages. It offers a precise way to
characterize regular languages and can be used to determine whether a given language L L is regular.
Additionally, it helps in identifying the minimum number of states in a DFA (Deterministic Finite
Automaton) that can recognize L L, provided L L is regular. This theorem forms the foundation of
efficient DFA minimization algorithms.

By applying the Myhill-Nerode theorem, we can also demonstrate examples for both regular and
non-regular languages. Moreover, the theorem can be used to show that for some languages, the small-
est possible DFA requires exponentially more states than the smallest possible NFA (Nondeterministic
Finite Automaton). This proves that the exponential increase in states during the subset construction
process is unavoidable, indicating that no more efficient general method exists to convert NFAs to
DFAs.

2 Statement of the Myhill-Nerode Theorem

The key idea in the Myhill-Nerode theorem is the concept of a distinguishing extension.

Definition 2.1: Let L ⊆ Σ∗ be a language over the alphabet Σ.

For any x,y ∈ Σ∗ , a string z ∈ Σ∗ is called a distinguishing extension of x and y if exactly one of the
strings xz or yz belongs to L (where xz is the concatenation of x and z). If such a string z exists, we
say that x and y are distinguishable by L; otherwise, they are indistinguishable by L.

The intuition behind this definition is as follows: Suppose L is a regular language recognized by a
DFA D. For any string s, let QD (s) represent the state of D after reading s. If QD (x) = QD (y), then
for any string z, we will have QD (xz) = QD (yz), meaning that D either accepts both xz and yz, or
rejects both. In this case, x and y are indistinguishable by L.

On the other hand, if QD (x) ̸= Q D (y) ,x and y might still be indistinguishable by L. In this
scenario, we say that the states QD (x) and QD (y) are equivalent, meaning they can be merged into
one state without changing the behavior of the DFA. However, if x and y are distinguishable by L,
then QD (x)and QD (y) will not be equivalent and cannot be combined.

1
 Proposition 2.2: Let L ⊆ Σ∗ be a language. Define ∼ L as a relation on Σ∗ , where x ∼ L y
if and only if x and y are indistinguishable by L. Then, ∼ L is reflexive, symmetric, and transitive,
meaning that ∼L is an equivalence relation on Σ∗ .
Recall that an equivalence relation ∼ on a set S creates equivalence classes, partitioning S into
subsets of elements related to each other by ∼. For example, let ∼ be a relation on the set of integers
Z defined by a ∼b if and only if a≡b(mod3). Then ∼ is an equivalence relation that divides Z into
three equivalence classes: [0], [1], and [2].

Remark 2.3: If x ∈ L and y ∈ L, then x and y are distinguishable by L; we can take the distin-
guishing extension to be the empty string ∈ . Thus, each equivalence class contains strings that are
either all in L or all not in L.

Remark 2.4: If L is regular and recognized by a DFA D, then x and y belong to the same equivalence
class of ∼ L. if and only if the states QD (x) and QD (y) are equivalent. If no states of the DFA D are
equivalent to each other, then x and y are in the same equivalence class if and only if QD (x)=QD (y)
. It follows that D has the minimal number of states possible. If L is regular and D is its minimal
DFA with states q0,q1,. . . ,qn , we can define the equivalence classes of ∼ L as the sets 〈i〉=w∈ Σ∗ QD
(w)=qi This gives the previous remark as a corollary.

We are now ready to state the theorem.

Theorem 2.5: Let L ⊆ Σ∗ be a language. Then, L is regular if and only if the number of equivalence
classes of ∼ L is finite. Furthermore, if L is regular, the number of equivalence classes of ∼ L is the
same as the number of states in the minimal DFA.Therefore, when discussing a regular language L, we
can reduce it to its most fundamental components: the equivalence classes of ∼ L , which correspond
to the minimal DFA for L. To show that a language L is not regular, we must prove that the number
of equivalence classes is infinite. This can be done by finding infinitely many strings such that no two
are equivalent (i.e., every pair is distinguishable by L).

3 Examples
Example 1:
Language: L1 = 0n 1n where n ≥ 1 (Strings of the form 0n 1n , where n is a positive integer)
Analysis:
For strings in L1, the Myhill-Nerode relation groups strings that behave similarly with respect to
membership in L1. Strings like 0n and 0m (where n ̸= m ) can be distinguished because if we add
the appropriate number of 1’s, one string will be in the language and the other won’t. .Therefore, for
every distinct n, we have a separate equivalence class, meaning there are infinitely many equivalence
classes. Conclusion: Since L1 has infinitely many equivalence classes, it is not regular.

Example 2: Regular Language Language: L2 = w ∈a,b∗ in w contains an even number of a’s

Analysis:
Let’s define the equivalence classes of L 2. We can distinguish between strings based on whether
they have an even or odd number of a’s.Two strings x and y are in the same equivalence class if
appending any additional string z to x and y results in both either being in the language or not.There
are two equivalence classes: Strings with an even number of a’s.Strings with an odd number of a’s.
Conclusion: Since L2 has a finite number of equivalence classes (just 2), it is regular.

Example 3: Language: L4 =w ∈ a,b∗ in w contains the substring ”ab” L4 =w∈a,b in w contains

the substring ”ab”
Analysis:
Strings in this language can be classified based on whether they contain the substring ”ab”.The DFA
for this language has a finite number of states because there are only a few relevant configurations:No
”a” has been seen yet.”a” has been seen but not followed by ”b”.”ab” has been seen, meaning the string
is already in the language.Since there are only three distinct equivalence classes, the language is regular.

2
 Conclusion: L4 has a finite number of equivalence classes, so it is regular.

4 Applications of Myhill Nerode Theorem

The Myhill-Nerode theorem has numerous significant applications in computer science, particularly
in the fields of formal language theory, automata theory, and compiler design. Here are some key
applications:

1. Proving Regularity of Languages The Myhill-Nerode theorem offers a straightforward method to

determine if a language is regular. According to the theorem, a language is regular if the number of its
equivalence classes is finite. By grouping strings into equivalence classes based on their distinguisha-
bility, we can easily verify whether a language can be represented by a deterministic finite automaton
(DFA).

2. Minimizing DFAs One of the crucial applications of the Myhill-Nerode theorem is in minimiz-
ing DFAs. The theorem provides a way to characterize the minimal DFA by stating that the number
of equivalence classes corresponds to the minimum number of states in the DFA for a regular language.

3. Proving Non-Regularity of Languages The theorem can also be used to demonstrate that certain
languages are not regular by showing that the language has an infinite number of equivalence classes.
This provides a strong tool for understanding the limitations of finite automata.
4. Designing Algorithms for DFA Minimization Efficient algorithms for DFA minimization, such as
Hopcroft’s algorithm, are based on the principles of the Myhill-Nerode theorem. These algorithms
systematically detect equivalent states and combine them to generate the smallest possible DFA.

5. Distinguishing Regular from Context-Free Languages Though the Myhill-Nerode theorem pri-
marily applies to regular languages, it can be used to separate regular languages from more complex
ones, such as context-free languages. By proving that a language has infinitely many equivalence
classes (and thus is not regular), researchers can determine what additional computational resources
are necessary to recognize the language (e.g., pushdown automata for context-free languages).

6. Text Processing and Search Algorithms In text processing, regular languages are often used to
define patterns for search algorithms (like regular expressions). The Myhill-Nerode theorem ensures
that these patterns are regular and can be matched efficiently using finite state automata.

7. Formal Grammar Analysis The theorem helps understand the structure and complexity of for-
mal grammars in language theory. For example, regular grammars can be characterized using the
Myhill-Nerode theorem, aiding in the classification of languages in the Chomsky hierarchy.

8. Finite State Machine Design in Hardware In digital circuit design, finite state machines (FSMs)
are used to model sequential logic. The Myhill-Nerode theorem can optimize these FSMs by minimizing
the number of states, reducing the hardware’s complexity.
The Myhill-Nerode theorem is a foundational tool in automata theory, language processing, compiler
design, hardware design, and formal verification. It provides both theoretical insight and practical
tools for optimizing and understanding the behavior of regular languages and their finite automaton
representations.