Course contentsShow
← Computer Science
Lesson 1808 of 2,87240. Theory of Computation: Regular LanguagesFree lesson

Myhill-Nerode Theorem: Equivalence Classes

Strings are equivalent if all suffixes lead to the same acceptance, partitioning the language.

Myhill-Nerode Theorem: Equivalence Classes

You'll learn how the Myhill-Nerode Theorem partitions all strings into equivalence classes based on their "future behavior."

The Core Idea

The Myhill-Nerode Theorem gives us another powerful way to understand regular languages. It says: two strings x and y are equivalent if, for every possible continuation (suffix) z, both strings either lead to acceptance or both lead to rejection.

In other words, if appending any string z to x has the same accept/reject outcome as appending z to y, then x and y are in the same equivalence class.

How It Works

Think of equivalence classes as "buckets" that group strings by their future potential:

  • Strings in the same bucket behave identically going forward
  • Once you know which bucket you're in, the past doesn't matter—only the remaining input affects acceptance
  • The number of buckets (equivalence classes) tells you whether a language is regular

Connection to DFAs: Each equivalence class corresponds to a state in the minimal DFA! When you read a string and end up in a particular DFA state, you've identified which equivalence class that string belongs to.

Example

For the language "strings containing 01 as a substring":

  • Equivalence class 1: strings that don't contain 01 yet and don't end in 0 (e.g., ε, 1, 11)
  • Equivalence class 2: strings that don't contain 01 yet but do end in 0 (e.g., 0, 10)
  • Equivalence class 3: strings that already contain 01 (e.g., 01, 101, 011)

All future suffixes will produce the same results within each class.

Key Takeaway: The Myhill-Nerode Theorem partitions strings into equivalence classes where members share identical acceptance behavior for all possible suffixes—the number of classes equals the number of states in the minimal DFA.