Ein pumpendes Lemma für deterministische kontextfreie Sprachen?

Das Pump-Lemma für reguläre Sprachen kann verwendet werden, um zu beweisen, dass bestimmte Sprachen nicht regulär sind, und das Pump-Lemma für kontextfreie Sprachen (zusammen mit Ogdens Lemma) kann verwendet werden, um zu beweisen, dass bestimmte Sprachen nicht kontextfrei sind.

Gibt es ein pumpendes Lemma für deterministische kontextfreie Sprachen? Das heißt, gibt es ein Lemma, das dem Pump-Lemma ähnelt und verwendet werden kann, um zu zeigen, dass eine Sprache keine DCFL ist? Ich bin neugierig, weil fast alle mir bekannten Beweistechniken, um zu zeigen, dass eine Sprache keine DCFL ist, wirklich kompliziert sind, und ich hatte gehofft, dass es eine einfachere Technik gibt.

Es gibt ein Pumping Lemma speziell für DCFL unter dem Titel "A Pumping Lemma for Deterministic Context-Free Languages" von Sheng Yu; Information Processing Letters 31 (1989) 47-51, doi 10.1016 / 0020-0190 (89) 90108-7 . Mit diesem expliziten Titel muss ich mich entschuldigen, dass ich ihn verpasst habe!

Die Online-Kopie hat leider eine leere Stelle in einer der Formeln, daher hoffe ich, dass ich das Ergebnis richtig rekonstruiert habe. Untenist das erste Symbol vony(wenn es existiert) oderε(wenny=ε).${}^{(1)}y$$y$$\varepsilon$$y=\varepsilon$

Lemma 1 (Pumping Lemma). Sei eine DCFL. Dann existiert eine Konstante C für L, so dass für jedes Wortpaar w , w ' ∈ if$L$$C$$L$$w,w'\in$

(1) [?] Und w ' = x z , | x | > C und$w=xy$$w'=xz$$|x|>C$

(2) , [?]${}^{(1)}y = {}^{(1)}z$

dann ist entweder (3) oder (4) wahr:

(3) es gibt eine Faktorisierung , | x 2 x 4 | ≥ 1 und | x 2 x 3 x 4 | ≤ C , so dass für alle i ≥ 0 x 1 x i 2 x 3 x i 4 x 5 y und x 1 x i 2$x=x_1x_2x_3x_4x_5$$|x_2x_4|\ge 1$$|x_2x_3x_4|\le C$$i\ge 0$ $x_1x^i_2x_3x^i_4x_5y$ sind in L ;$x_1x^i_2x_3x^i_4x_5z$$L$

$x=x_1x_2x_3$$y=y_1y_2y_3$$z=z_1z_2z_3$$|x_2|\ge 1$$|x_2x_3|\le C$$i\ge 0$ $x_1x^i_2x_3y_1y^i_2y_3$$x_1x^i_2x_3z_1z^i_2z_3$$L$

$\{ a^ib^i \mid i\ge 0 \} \cup \{ a^ib^{2i} \mid i\ge 0 \}$$\{ w\in\{a,b\}^* \mid w=uv, |u|=|v|, \mbox{ and } v \mbox{ contains an } a \}$sind nicht DCFL. Der Beweis nutzt die Tatsache, dass jede DCFL eine LR (1) -Grammatik in Greibach-Normalform hat.