[Solved]: Why is deciding regularity of a context-free language undecidable?

Problem Detail: 

As I have studied, deciding regularity of context-free languages is undecidable.

However, we can test for regularity using the Myhill–Nerode theorem which provides a necessary and sufficient condition. So the problem should be decidable.

Where is my mistake?

Asked By : Jiya

Answered By : David Richerby

Myhill–Nerode does indeed provide a characterization of the regular languages but that isn't enough to show that the problem is decidabe. "Decidable" means that there is an algorithm (more formally, a Turing machine) that terminates for every input and, of course, always gives the correct answer. So, in this case, you would need to give an algorithm that, given a language as input, determines whether the Myhill–Nerode relation has a finite number of equivalence classes. It turns out that this cannot be done for context-free languages; details in your favourite formal languages textbook.

If you want to decide whether a general language is regular, a further subtlety is that you have to be careful about what is the input to your algorithm. The input must be a finite string – otherwise, even just reading the input would be a non-terminating algorithm. In the case of context-free languages, you could use a grammar as a finite representation of an infinite language. For more general languages, you would need... well, something more general. Ultimately, though, if you want to deal with all languages, you're doomed. Over any finite alphabet, there are uncountably many languages but only countably many finite strings. That means you can't possibly describe all languages using finite strings.¹ Therfore, trying to write an algorithm to determine whether arbitrary languages given as input are regular actually fails before it begins. It's not just that you can't write the algorithm: you can't even write the input!

Note that this doesn't mean that you, a human being, can't use Myhill–Nerode to determine whether languages are regular. It just means that you can't write down a set of precise instructions to tell me how to do that. At some point, any such set of instructions would have to say something like, "And then play about with it to see what works," or "From there, you have to figure it out on your own."

---

1. In particular, this means that some languages must be undecidable, since there are more languages than there are algorithms.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/19482