Ein pumpendes Lemma für deterministische kontextfreie Sprachen?

11

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.

templatetypedef
quelle
2
Es gibt einige verwandte Fragen , die relevant sein können oder nicht.
Raphael
Informatiker mögen Sadisten sein, aber sie sind nicht alle Masochisten, die
überkomplizierte
1
vonbrand: Aber jeder Mathematiker oder Informatiker könnte überkomplizierte Beweisverfahren anwenden, wenn ihm einfachere noch nicht bekannt oder nicht bekannt sind.
Blaisorblade

Antworten:

9

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)yyεy=ε

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

(1) [?] Und w ' = x z , | x | > C undw=xyw=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 xx=x1x2x3x4x5|x2x4|1|x2x3x4|Ci0 x1x2ix3x4ix5y sind in L ;x1x2ix3x4ix5zL

x=x1x2x3y=y1y2y3z=z1z2z3|x2|1|x2x3|Ci0 x1x2ix3y1y2iy3x1x2ix3z1z2iz3L

{aibii0}{aib2ii0}{w{a,b}w=uv,|u|=|v|, and v contains an a}sind nicht DCFL. Der Beweis nutzt die Tatsache, dass jede DCFL eine LR (1) -Grammatik in Greibach-Normalform hat.

Hendrik Jan.
quelle
Ich hoffe du kannst es benutzen. Die Angabe ist noch komplizierter als das bekannte Pump-Lemma.
Hendrik Jan