An analog of the Myhill-Nerode Theorem for context-free languages?

The Myhill-Nerode Theorem gives an exact characterization of the regular languages. Given any language, one can check whether it meets the criteria of the Myhill-Nerode theorem to decide whether or not it is regular. Note that this is stronger than the pumping lemma for regular languages, which gives a necessary (but not sufficient) condition for a language to be regular.

Is there an analogous result for context-free languages? That is, is there a theorem that gives a necessary and sufficient condition for a language to be context-free?

Thanks!

Solution 1:

This is probably not really what you are looking for, but it's the best I know. It's a strengthening of the fairly well-known Parikh's Theorem.

There is a characterisation of the bounded context-free languages. A language $L$ is bounded if $L\subseteq w_1^* w_2^* \ldots w_n^*$ for some fixed words $w_1,\ldots,w_n$, in which case we can define a corresponding subset of $\mathbb{N}_0^n$:

$\Phi(L) = \{(m_1,m_2,\ldots,m_n) \mid w_1^{m_1} w_2^{m_2} \ldots w_n^{m_n}\in L\}.$

By a theorem of Ginsburg and Spanier (Thm 5.4.2 in Ginsburg's book 'The Mathematical Theory of Context-free Languages'), a bounded language $L$ is context-free if and only if $\Phi(L)$ can be expressed as a finite union of linear sets, each with a stratified set of periods. For the definitions of the terms in the last sentence, see my MO question.

This characterisation can be very useful for proving (not necessarily bounded) languages not to be context-free. If we can find words $w_1,\ldots,w_n$ such that $L\cap w_1^*\ldots w_n^*$ is not context-free, then $L$ is not context-free either, since $w_1^*\ldots w_n^*$ is a regular language, and the intersection of a context-free language with a regular language is context-free.

Solution 2:

Myhill-Nerode theorem is very closely related to the following theorem: language $L$ is regular if and only if its syntactic monoid is finite. This also gives you precise characterization of regular languages. Moreover, majority of definitions regarding regular languages can be nicely translated to group theory.

To answer you question, the mentioned theorem can be generalized a bit, i.e. a group is context-free if and only if it contains a finitely generated free subgroup of finite index (compare with this article). Unfortunately this doesn't make anything easier, still it is a characterization of context-free languages that are word problem for some group (to be clear those are not the all context-free languages).

Hope this helps ;-)

Edit: fixed broken link.

Edit 2: made clear that those are not the only context-free languages. Loony me, it must have been a bad digestion (and the phase of the moon too, naturally), that made me write the previous version, sorry for that!