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?
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,
- Undecidable Problems for Context-free Grammars, by Hendrik Jan Hoogeboom
Deciding whether a context-free language is regular [closed], on the Theoretical Computer Science Stack Exchange, in which user babou lists
- A regularity test for pushdown machines, R.E. Stearns, Information and Control, 1967 (full text by clicking on the page)
- Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. Valiant, JACM 1975
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).