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$
$\endgroup$
1
-
$\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$– John L.Feb 28, 2019 at 0:44
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
5
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
answered Feb 27, 2019 at 19:05
-
$\begingroup$ Is it a failure of this site that you have been participating for 6 years no reference from this site is chosen? $\endgroup$– John L.Feb 27, 2019 at 19:16
-
2$\begingroup$ Not at all, but i didn't want to refer to myself. $\endgroup$ Feb 27, 2019 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$ Feb 28, 2019 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$ Feb 28, 2019 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$ Feb 28, 2019 at 19:48
$\begingroup$
$\endgroup$
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).
answered Feb 28, 2019 at 11:00