8
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ How do you propose to tell whether the Myhill-Nerode relation has a finite number of equivalence classes? What property of context-free languages do you think allows you to do that? $\endgroup$ – David Richerby Jan 3 '14 at 13:01
  • 2
    $\begingroup$ Please check the definition of computability: you need to give a Turing machine (or, more generally, an algorithm) that solves the problem (always). Myhill-Nerode is, per se, not an algorithm, only a characterisation. Is the provided property decidable? Have you tried transforming the theorem into such an algorithm? $\endgroup$ – Raphael Jan 4 '14 at 18:41
  • 2
    $\begingroup$ @Jiya What do you mean by "decide regularity"? At first, it seems obvious what that means but it's actually more subtle. A decision procedure (algorithm) must take a finite input so how would you give an infinite language as input? Maybe you want to use expressions such as $\{a^nb^n\mid n\ge 0\}$. OK, but what expressions will you allow? $\{a^nb^m\mid \text{the }m\text{th Turing machine halts on input }m\}$? $\{a^nb^{kn}\mid k\text{ is one of David Richerby's favourite numbers}\}$? $\endgroup$ – David Richerby Jan 4 '14 at 22:19
  • 1
    $\begingroup$ @Jiya Absolutely, yes. But you have to choose what set of expressions you want to accept and write a formal specification of those expressions. Then, your Turing machine would have to parse the expressions and decide whether they correspond to regular languages or not. $\endgroup$ – David Richerby Jan 5 '14 at 12:13
  • 1
    $\begingroup$ @Jiya If the only languages you consider are the ones of the form $\{a^{kx}b^{\ell x}c^{mx}|x\ge 0\}$ where $k$, $\ell$ and $m$ are constants, then the resulting language is regular if, and only if, two or three of $k$, $\ell$ and $m$ are zero. So, for languages defined that way, the problem of determining whether the resulting language is regular is decidable. But, if you allow more complex relationships between the numbers of $a$s, $b$s and $c$s, it can be undecidable whether a language is regular. This is why it is crucially important how the languages are specified. $\endgroup$ – David Richerby Jan 6 '14 at 17:18
9
$\begingroup$

Myhill–Nerode does indeed provide a characterization of the regular languages but that isn't enough to show that the problem is decidable. "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.1 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.
| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ We can circumvent the problem with input encoding by restricting ourselves to all recursively enumerable, or decidable, or even context-free languages. Then, we have "natural" input encodings (grammars, Turing machines, ...) but still can not decide regularity. So, clearly, there are more subtle things afoot. $\endgroup$ – Raphael Jan 5 '14 at 16:56
  • $\begingroup$ Thanks Raphael. I've edited to make it clearer that the "doom" section referred to not being able to accept all languages as inputs. $\endgroup$ – David Richerby Jan 5 '14 at 17:24

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.