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 http://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.
Asked By : András Salamon
Answered By : Yuval Filmus
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.
More information on the strong pumping lemma appears in one of my answers.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12643
0 comments:
Post a Comment
Let us know your responses and feedback