# Myhill-Nerode style characterization of CFL?

Define the Nerode equivalence over a language $L \subseteq \Sigma^{*}$ as $u \sim_L v$ iff $uw \in L \Leftrightarrow vw \in L$ for every $w \in \Sigma^{*}$.

The Nerode equivalence ${\sim}_L$ has finitely many equivalence classes precisely when $L$ can be recognized by a finite-state automaton. This is the Myhill-Nerode theorem.

Is there a similar characterization of context-free languages?

# Motivation:

The Nerode equivalence classes each correspond to a distinct state in any automaton that recognizes $L$. Each CFL can be recognized by an NPDA, which has a finite number of states but also a potentially unbounded stack of alphabet symbols. The stack keeps track of one possible way that a string can be parsed. The number of equivalence classes may be infinite since the stack can store an unbounded number of symbols.

I am asking: is there always a way to clump together equivalence classes so that each clump represents one state of the PDA, with each class within the clump representing equivalent states of the stack for that PDA state?

For instance, the language of properly nested parentheses only needs states to handle pop and push, as the stack will keep track of the current nesting depth. If such clumping can always be done, then whether the number of clumps is finite determines whether the language is context-free.

As pointed out by @sdcvvc in a comment, a form of this question was asked as https://math.stackexchange.com/questions/118362 although Yuval Filmus's answer to the related question at Example of a non-context free language that nonetheless CAN be pumped? is more relevant.

• – sdcvvc Jun 13 '13 at 0:19

David S. Wise provides in his paper A strong pumping lemma for context-free languages a strong pumping lemma which is equivalent to being context-free. He also provides an additional equivalent condition (property 3 on page 362) which he claims could be viewed as an analog of the Myhill-Nerode theorem. As an application of the latter, he shows that $\{ a^nba^{mn} : m,n > 0 \}$ cannot be expressed as a finite intersection of context-free languages.

The polynomial closure $Pol(\mathcal{L})$ of a class $\mathcal{L}$ of languages of $A^*$ is the set of all languages that are finite unions of products of the form $L_0a_1L_1 \dotsm a_nL_n$, where $L_0, ..., L_n \in \mathcal{L}$ and $a_1, ..., a_n \in A$.
An algebra is a class $\mathcal{A}$ of languages containing the language $\{1\}$ and such that $\mathcal{A} = Pol(\mathcal{A})$. It is finitely generated if $\mathcal{A} = Pol(\mathcal{F})$ for some finite set $\mathcal{F}$ of languages. It is stable if, for each $L \in \mathcal{A}$ and $u \in A^*$, the language $u^{-1}L = \{v \mid uv \in L\}$ also belongs to $\mathcal{A}$. Note that it suffices to have $a^{-1}L \in \mathcal{A}$ for all $a \in A$.
Theorem. A language of $A^*$ is context-free if and only if it belongs to a finitely generated stable algebra.