A pumping lemma for deterministic context-free languages?

Problem Detail: The pumping lemma for regular languages can be used to prove that certain languages are not regular, and the pumping lemma for context-free languages (along with Ogden’s lemma) can be used to prove that certain languages are not context-free. Is there a pumping lemma for deterministic context-free languages? That is, is there a lemma akin to the pumping lemma that can be used to show that a language is not a DCFL? I’m curious because almost all of the proof techniques I know to show that a language is not a DCFL are really complicated, and I was hoping that there was an easier technique.

Asked By : templatetypedef

Answered By : Hendrik Jan

There is a Pumping Lemma specifically for DCFL, under the title “A Pumping Lemma for Deterministic Context-Free Languages”, by Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016/0020-0190(89)90108-7. With this explicit title I must apologize that I missed it! The online copy unfortunately has a blank spot in one of the formula, so I hope I reconstructed the result properly. Below ${}^{(1)}y$ is the first symbol of $y$ (when it exists). Lemma 1 (Pumping Lemma). Let $L$ be a DCFL. Then there exists a constant $C$ for $L$ such that for any pair of words $w,w’in $ if (1) $w=xy$ [?] and $w’=xz$, $|x|>C$ and (2) ${}^{(1)}y neq {}^{(1)}z $, [?] then either (3) or (4) is true: (3) there is a factorization $x=x_1x_2x_3x_4x_5$, $|x_2x_4|ge 1$ and $|x_2x_3x_4|le C$, such that for all $ige 0$ $x_1x^i_2x_3x^i_4x_5y$ and $x_1x^i_2x_3x^i_4x_5z$ are in $L$; (4) there exist factorizations $x=x_1x_2x_3$, $y=y_1y_2y_3$ and $z=z_1z_2z_3$, $|x_2|ge 1$ and $|x_2x_3|le C$, such that for all $ige 0$ $x_1x^i_2x_3y_1y^i_2y_3$ and $x_1x^i_2x_3z_1z^i_2z_3$ are in $L$. Two applications of the Lemma are given: ${ a^ib^i mid ige 0 } cup { a^ib^{2i} mid ige 0 }$ as well as ${ win{a,b}^* mid w=uv, |u|=|v|, mbox{ and } v mbox{ contains an } a }$ are not DCFL. The proof uses the fact that each DCFL has an LR(1) grammar in Greibach normal form.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10974