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?


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.