12
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ There are some related questions that may or may not be relevant. $\endgroup$
    – Raphael
    Apr 2, 2013 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, 2013 at 16:39
  • 1
    $\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$ May 13, 2013 at 20:56

1 Answer 1

10
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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