In my theory of computing class, we've been talking about how to prove languages regular and non-regular. I've heard of methods like the pumping lemma and Kolmogorov complexity to prove languages non-regular, while proving languages regular revolves around building a DFA, or using the Myhill-Nerode theorem. All of these approaches fail for some language. Is there some approach that will work for all regular/non-regular languages?

  • $\begingroup$ It looks like you have an inkling of what is going to come in your computing class. There will be quite a few theorems and facts stating that there is no general approach for many problems. The key word is "decidability" or "undecidability". $\endgroup$ – Apass.Jack Feb 28 at 0:44

No, there isn't. It is undecidable, even for context-free languages. It is decidable for deterministic context-free languages.

References are easy to find with Google; for instance,

  • $\begingroup$ Is it a failure of this site that you have been participating for 6 years no reference from this site is chosen? $\endgroup$ – Apass.Jack Feb 27 at 19:16
  • 2
    $\begingroup$ Not at all, but i didn't want to refer to myself. $\endgroup$ – reinierpost Feb 27 at 19:21
  • 1
    $\begingroup$ @Apass.Jack In fact, if you like recursion, the first link "Undecidable problems .." has an acknowledgement: "Parts of this overview were inspired by answers on stackexchange, like for instance by users reinierpost and Sylvain." $\endgroup$ – Hendrik Jan Feb 28 at 10:29
  • $\begingroup$ If you have written good answers explaining these things, please link to them. There is nothing wrong with self-citation, as long as the cited material is relevant. It's just not helpful to deliberately write an answer that is less good than you could easily make it. $\endgroup$ – David Richerby Feb 28 at 11:01
  • $\begingroup$ All I've done is referred to Hendrik Jan's overview in another answer but to a different question. I've searched harder, and I can't find a duplicate of the exact question above on this site. $\endgroup$ – reinierpost Feb 28 at 19:48

Yes. Myhill–Nerode works for every language: every regular language has a finite number of equivalence classes, and every non-regular language has an infinite number.

However, there is no general method for actually using Myhill–Nerode. Like all mathematical proofs, creativity is needed to find the equivalence classes. As reinierpost says, there is no algorithm you can use to determine whether a context-free grammar produces a regular language (i.e., one with a finite number of Myhill–Nerode classes).


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.