Questions: Myhill-Nerode Theorem

Question 1

For language L = {w ∈ {0,1}* | w ends in '1'}, are the strings '01' and '111' Myhill-Nerode equivalent?

• A. No, because the strings have different lengths and different content
• B. Yes, because both strings end in '1', and any suffix appended produces the same accept/reject outcome for both
• C. No, because '01' has fewer 1s than '111', which affects acceptance of continuations
• D. Yes, because both strings are accepted by L, so they must be in the same equivalence class

Answer: (B)

Two strings are Myhill-Nerode equivalent if no suffix can distinguish them: for every z, xz ∈ L ↔ yz ∈ L. Both '01' and '111' end in 1. For any suffix z: if z is empty, both are in L; if z ends in 0, neither is in L; if z ends in 1, both are in L. No suffix distinguishes them, so they are equivalent. Option D is wrong — acceptance of the strings themselves does not determine equivalence; equivalence is about identical behavior under *all* extensions, including those that push them outside L.

Question 2

To prove that L = {aⁿbⁿ | n ≥ 0} is not regular using the Myhill-Nerode theorem, you would:

• A. Show that the language cannot be expressed as a regular expression
• B. Exhibit infinitely many strings that are pairwise Myhill-Nerode distinguishable — each pair separated by some suffix — proving the language requires infinitely many equivalence classes
• C. Show that any DFA for L requires at least n+1 states for inputs of length 2n, so the minimal DFA grows without bound
• D. Apply the pumping lemma to a string in L and show that any pumping produces a string outside L

Answer: (B)

The Myhill-Nerode approach is direct: for each i ≠ j, strings aⁱ and aʲ are distinguishable by the suffix bⁱ — because aⁱbⁱ ∈ L but aʲbⁱ ∉ L. Since a, a², a³, ... are all pairwise distinguishable, there are infinitely many equivalence classes, so L is not regular. Option C describes a consequence but not the proof technique. Option D (pumping lemma) also works but is typically less direct and less illuminating than identifying concrete distinguishing suffixes.

Question 3

If two strings reach the same state in the minimal DFA for language L, they are Myhill-Nerode equivalent.

• T. True
• F. False

Answer: True

The Myhill-Nerode theorem establishes an exact correspondence: each equivalence class under ≡_L corresponds to exactly one state in the minimal DFA. Two strings reach the same state if and only if no suffix can distinguish their futures — precisely the definition of Myhill-Nerode equivalence. In a non-minimal DFA, equivalent strings might land in different (redundant) states; but the *minimal* DFA collapses all equivalent strings into one state. This is why the minimal DFA is unique: its states are determined by the language itself, not by any design choice.

Question 4

A regular language can have infinitely many Myhill-Nerode equivalence classes, as long as the DFA recognizing it has finitely many states.

• T. True
• F. False

Answer: False

The Myhill-Nerode theorem states the equivalence in both directions: a language is regular *if and only if* the number of equivalence classes under ≡_L is *finite*. Moreover, that number exactly equals the number of states in the minimal DFA. A regular language recognized by a DFA with n states has exactly n equivalence classes — no more. If a language has infinitely many equivalence classes, it cannot be regular and no finite automaton can recognize it, regardless of construction.

Question 5

What does the number of Myhill-Nerode equivalence classes for a language tell you, and why is this significant?

Model answer: The number of equivalence classes equals the number of states in the minimal DFA for the language — if finite. Each class corresponds to one state representing everything the automaton needs to remember about the input seen so far. This is significant because it shows the minimal DFA is uniquely determined by the language itself, not by any particular construction, and reveals the fundamental 'memory requirement' of the language: how many distinct situations the automaton must distinguish to correctly classify all inputs. A language requiring infinitely many classes cannot be regular.

The Myhill-Nerode theorem gives regularity a characterization purely in terms of the language's structure — independent of any machine model. This makes it both a theoretical foundation and a practical tool: computing equivalence classes is the basis for DFA minimization algorithms, and exhibiting infinite classes is often the cleanest proof of non-regularity.