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.