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.

  • 1
    $\begingroup$ There are some related questions that may or may not be relevant. $\endgroup$ – Raphael Apr 2 '13 at 15:54
  • $\begingroup$ Computer scientists may be sadists, but they aren't are all masochists who use over-complicated proof techniques where simpler ones are known... $\endgroup$ – vonbrand Apr 2 '13 at 16:39
  • $\begingroup$ 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. $\endgroup$ – Blaisorblade May 13 '13 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.

  • $\begingroup$ I hope you can use it. It is even more complicated to state than the known pumping lemma. $\endgroup$ – Hendrik Jan Apr 12 '13 at 21:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.