# Why is deciding regularity of a context-free language undecidable?

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?

• 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? Jan 3 '14 at 13:01
• 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?
– Raphael
Jan 4 '14 at 18:41
• @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}\}$? Jan 4 '14 at 22:19
• @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. Jan 5 '14 at 12:13
• @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. Jan 6 '14 at 17:18