# A pumping lemma for deterministic context-free languages?

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.

• There are some related questions that may or may not be relevant.
– Raphael
Apr 2, 2013 at 15:54
• Computer scientists may be sadists, but they aren't are all masochists who use over-complicated proof techniques where simpler ones are known... Apr 2, 2013 at 16:39
• vonbrand: But any mathematician or computer scientist might use over-complicated proof techniques if simpler ones are not yet known or not known to him. May 13, 2013 at 20:56

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) or $$\varepsilon$$ (if $$y=\varepsilon$$).

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 = {}^{(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 $$i\ge 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 $$i\ge 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 i\ge 0 \} \cup \{ a^ib^{2i} \mid i\ge 0 \}$$ as well as $$\{ w\in\{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.

• I hope you can use it. It is even more complicated to state than the known pumping lemma. Apr 12, 2013 at 21:04