Kann es ein kontextsensitives Pump-Lemma geben?

8

Es ist bekannt, dass eine "Pump" -Eigenschaft (Wörter einer bestimmten Länge implizieren das Vorhandensein von Schleifen im sprachdefinierenden Mechanismus) für reguläre und kontextfreie Sprachen und einige weitere (normalerweise verwendet, um die Zugehörigkeit einer Sprache zu einer bestimmten Klasse zu widerlegen) existiert ).

In der Diskussion um diese Frage deutet Daisys Antwort darauf hin, dass es für kontextsensitive Sprachen kein pumpendes Lemma geben kann - da sie so komplex sind.

Ist das wahr - kann gezeigt werden, dass es keine Pumpeigenschaft geben kann - und gibt es eine gute Referenz dafür (oder dagegen)?

lukas.coenig
quelle
2
Können Sie eine formale Definition von "Pumping Lemma" geben? Wenn nicht, kann es grundsätzlich keinen solchen Beweis geben.
Raphael
Vielleicht kann man Parikhs Theorem für kontextsensitive Sprachen widerlegen, und dies lässt uns erwarten, dass es kein pumpendes Lemma gibt, das denjenigen ähnelt, die wir kennen.
Yuval Filmus
@ YuvalFilmus Was meinst du? Offensichtlich sind die Primzahlen kontextsensitiv und nicht semilinear. Parikh gilt also nicht für kontextsensitiv. Das bedeutet, dass "lineares Pumpen" nicht gilt. Wie Raphael bin ich gespannt, welche anderen Methoden als Pumpen gelten würden.
Hendrik
1
Sie haben Recht, es kommt darauf an zu wissen, was genau "Pumpen" ist ... Ich hatte auf einige Vorschläge gehofft ... Was ist Parikhs Theorem für kontextsensitive Sprachen ? Ich habe nur eine für kontextfreie Sprachen gefunden.
lukas.coenig
1
@ lukas.coenig Es gibt keinen Parikh-Satz für kontextsensitive Sprachen, aber es könnte einen gegeben haben, wenn es ein einfaches Pump-Lemma für kontextsensitive Sprachen gegeben hätte.
Yuval Filmus

Antworten:

8

Hier gibt es einige Hinweise darauf, dass es für die kontextsensitiven Sprachen kein Pump-Lemma gibt.

Eine Antwort hängt natürlich von der Frage ab, was ein Pump-Lemma ausmacht. Die schwächste vernünftige Definition, die ich mir vorstellen kann, ist folgende: Eine Sprachklasse hat ein Pump-Lemma, wenn es ein entscheidbares ternäres Prädikat P ( , , ) gibt, wobei P ( g , w , d ) bedeutet:CP(,,)P(g,w,d)

  • ist ein Wort, das eine Sprache L ( g ) aus C codiert(denke: Grammatik),gL(g)C
  • ist ein Wort in der von g codierten Sprachewg
  • ist ein Wort, das einepumpbareBerechnung / Ableitung für w codiert(denken Sie: NFA-Berechnung mit wiederholtem Zustand oder CFG-Ableitungsbaum mit wiederholtem Nichtterminal). HierpumpbarenMittel: Es gibt unendlich viele Wörter in L ( g ) .dwL(g)

Darüber hinaus wollen wir, dass bei gegebener Sprache in C , die von g codiert wird , für jedes ausreichend lange Wort ein Wort so dass P ( g , w , d ) .LCgdwLdP(g,w,d)

Zum Beispiel würde das Pump-Lemma für reguläre Sprachen das Prädikat " codiert eine ε- freie NFA und d codiert einen Lauf, der einen Zustand wiederholt und w liest " hervorrufen . Für geeignete Codierungen erfüllt dies eindeutig die obigen Bedingungen.gεdw

Lassen Sie uns nun zeigen, dass ein solches Prädikat für die kontextsensitiven Sprachen nicht existiert.

Beachten Sie, dass, wenn eine Sprachklasse ein Pump-Lemma hat, das Unendlichkeitsproblem (bei gegebener Grammatik eine unendliche Sprache erzeugt?) Rekursiv aufzählbar ist: Bei einer Codierung können wir die Wörter w und d aufzählen und prüfen, ob P ( g , w , d ) . Wenn wir ein solches w , d gefunden haben , antworten wir mit "Ja", andernfalls setzen wir die Aufzählung fort.gwdP(g,w,d)w,d

Wir zeigen jedoch, dass das Unendlichkeitsproblem für die kontextsensitiven Sprachen nicht rekursiv aufzählbar ist. Denken Sie daran, dass eine Ebene der arithmetischen Hierarchie ist, die die rekursiv aufzählbaren Sprachen streng einschließt. Daher genügt es zu beweisen:Π20

Behauptung : Das Unendlichkeitsproblem für die kontextsensitiven Sprachen ist -vollständig.Π20

Es ist bekannt, dass das Unendlichkeitsproblem für rekursiv aufzählbare Sprachen -vollständig ist (häufiger findet man die Formulierung, dass das Endlichkeitsproblem Σ 0 2 -vollständig ist). Daher reicht es aus, das letztere Problem auf das Unendlichkeitsproblem für die kontextsensitiven Sprachen zu reduzieren.Π20Σ20

Bei gegebenem TM konstruieren wir einen LBA A für die Sprache { u # v v  ist eine Shortlex-Minimal-Akzeptanzberechnung von  M  bei Eingabe  u } . Dann ist L ( A ) unendlich, wenn L ( M ) unendlich ist, was unseren Beweis vervollständigt.MA

{u#vv is a shortlex-minimal accepting computation of M on input u}.
L(A)L(M)

Update: Versucht, klarer zu sein. Update: Beispiel hinzugefügt.

Georg Zetzsche
quelle
Lassen Sie uns diese Diskussion im Chat fortsetzen .
Raphael