[Math] Show a language is regular with Myhill-Nerode Theorem

automatacomputer scienceequivalence-relationsregular-language

I understand how to show a language is not regular using Myhill-Nerode Theorem (proof by contradiction), but how do you show the language is regular?

Take language $0^*1^*$ for example. I know this language is regular (I can build a dfa), but how do I apply Myhill-Nerode?

Best Answer

The Myhill-Nerode Theorem says that a language $L$ is regular if and only if the number of equivalences classes of the relation $R_L$ is finite, where $$ x R_L y \iff x, y \text{ have no distinguishing extension.} $$ (Terminology and notation are as in the article you cite.) In the case of $0^*1^*$, it's not hard to show that the equivalence classes are:

  • the equivalence class of $\varepsilon$, which equals the eq. class of $0$,
  • the equivalence class of $1$, and
  • the equivalence class of strings not in the language.

There are three, so the language is regular. The theorem also says that when $L$ is regular, the number of equivalence classes equals the minimum number of states of DFAs recognizing the language. Probably the DFA you figured out is that minimal DFA.

Related Question