Beweis des Pumplemmas für kontextfreie Sprachen mit Pushdown-Automaten

21

Das pumpfähige Lemma für reguläre Sprachen kann durch Betrachtung eines Automaten mit endlichen Zuständen bewiesen werden, der die untersuchte Sprache erkennt, eine Zeichenfolge mit einer Länge auswählt, die größer als die Anzahl der Zustände ist, und das Taubenlochprinzip anwendet. Das pumpfähige Lemma für kontextfreie Sprachen (sowie Ogdens Lemma, das etwas allgemeiner ist) wird jedoch bewiesen, indem eine kontextfreie Grammatik der untersuchten Sprache betrachtet, eine ausreichend lange Zeichenfolge ausgewählt und der Analysebaum betrachtet wird.

Angesichts der Ähnlichkeit der beiden Pumplemmas würde man erwarten, dass das kontextfreie auch auf ähnliche Weise wie das reguläre nachgewiesen werden kann, indem ein Pushdown-Automat in Betracht gezogen wird, der die Sprache anstelle einer Grammatik erkennt. Es gelang mir jedoch nicht, einen Hinweis auf einen solchen Beweis zu finden.

Daher meine Frage: Gibt es einen Beweis für das Pumplemma für kontextfreie Sprachen, der nur Pushdown-Automaten und keine Grammatiken umfasst?

a3nm
quelle

Antworten:

16

Ich habe wieder über dieses Problem nachgedacht und denke, ich habe einen vollständigen Beweis. Es ist etwas kniffliger als ich erwartet hatte. Kommentare sind sehr willkommen! Update: Ich habe diesen Proof auf arXiv eingereicht, falls dies für jemanden nützlich ist: http://arxiv.org/abs/1207.2819

Sei eine kontextfreie Sprache über einem Alphabet . Sei ein Pushdown-Automat, der mit Stack-Alphabet erkennt . Wir bezeichnen mitdie Anzahl der Zustände von A . Ohne Verlust der Allgemeinheit können wir davon ausgehen, dass Übergänge von A das oberste Symbol des Stapels platzieren und entweder kein Symbol auf den Stapel oder das vorherige oberste Symbol und ein anderes Symbol auf den Stapel schieben.L LΣ ΣA AL LΓ Γ| A | |A|A AAA

Wir definierenund die Pumplänge und zeigt, dass alle so sind, dass haben eine Zerlegung der Form so dass , und .p ' = | A | 2 | Γ | p = | A | ( | Γ | + 1 ) p w L | w | > p w = u v x y z | v x y | p | v y | 1 n 0 , u v n xp=|A|2|Γ|p=|A|(|Γ|+1)pwL|w|>pw=uvxyz|vxy|p|vy|1y n z Ln0,uvnxynzL

Sei so, dass . Sei ein akzeptierender Pfad minimaler Länge für (dargestellt als Folge von Übergängen von ), so bezeichnen wir seine Länge mit. Wir können für, die Größe des Stapels an der Position des akzeptierenden Pfades. Für alle definieren wir einen Pegel über als eine Menge von drei Indizes mit so dass:w L wL| w | > p |w|>pπ πw wA A| π | |π|0 i < | π | 0i<|π|s isi i iN > 0 N>0NN π πi , j , k i,j,k0 i < j < k p0i<j<kp

  1. s i = s k , s j = s i + Nsi=sk,sj=si+N
  2. für alle so, dass ,n i n j s is ns jninjsisnsj
  3. für alle so, dass , .n j n k s ks ns knjnksksnsk

(Ein Beispiel hierfür finden Sie in der Abbildung für Fall 2, in der ein Level dargestellt ist.)NN

Wir definieren das Niveau von als das maximale so dass ein Niveau hat . Diese Definition wird durch die folgende Eigenschaft motiviert: wenn die Größe des Stapels über einen Pfad größer als sein Pegel , dann wird die Stapel Symbole mehr als Ebene wird tief nie geknallt werden. Wir unterscheiden nun zwei Fälle: entweder , wobei wir wissen , dass die gleiche Konfiguration für den Automaten Zustand und die obersten Symbole des Stapels zweimal in der ersten auftreten Stufe von , oderl π N π N π l l l < p ' l p + 1 π l p 'lπNπNπlll<plp+1πlpund es muss eine Stapel- und Entstapelungsposition geben, die beliebig oft wiederholt werden kann, aus der wir und konstruieren .v yvy

Fall 1. . Wir definieren die Konfigurationen von , wie die Paare von einem Zustand und einer Folge von Stapel Symbole (wo Stapel von Größe von weniger als mit durch sie zu Klotzen dargestellt werden mit einem speziellen leeren Symbol, weshalb wir verwenden bei der Definition von ). Per Definition gibt es solche Konfigurationen, die kleiner als . In den ersten Schritten von wird dieselbe Konfiguration also zweimal an zwei verschiedenen Positionen angetroffen, z. B. . Bezeichnen mitl < p ' A A l l l | Γ | + 1 p | A | ( | & Ggr; | + 1 ) l p p + 1 π i < j il<pAAlll|Γ|+1p|A|(|Γ|+1)lpp+1πi<jiˆ (bzw. ) die Position des letzten Buchstabens von , der in Schritt (bzw. ) von gelesen wurde . Wir haben . Wir können also mit , , , . (Mit bezeichnen wir die Buchstaben von von einschließlich bis ausschließlich.) Mit .ˆjjˆwwiijjππˆiˆjiˆjˆw=uvxyzw=uvxyzyz=ϵyz=ϵu=w0ˆiu=w0iˆv=wˆiˆjv=wiˆjˆx=wˆj|w|x=wjˆ|w|wxywxywwxxyy|vxy|p|vxy|p

Wir müssen auch zeigen, dass , aber dies folgt aus unserer obigen Beobachtung: Stapelsymbole, die tiefer als sind, werden niemals gesprungen, so dass es keine Möglichkeit gibt, zu unterscheiden Konfigurationen, die gemäß unserer Definition gleich sind, und ein akzeptierender Pfad für wird aus dem von indem die Schritte zwischen und , mal wiederholt werden .n0,uvnxynz=uvnxLn0,uvnxynz=uvnxLlluvnxuvnxwwiijjnn

Schließlich haben wir auch , denn wenn , dann, weil wir die gleiche Konfiguration in den Schritten haben und in , wäre ein akzeptierender Weg für , der der Minimalität von widerspricht .|v|>0|v|>0v=ϵv=ϵiijjπππ=π0iπj|π|π=π0iπj|π|wwππ

(Beachten Sie, dass dieser Fall beträgt das Pumping - Lemma für reguläre Sprachen auf die Anwendung von hartzucodieren die obersten Stapel Symbole in den Automaten Zustand, der ausreichend ist , weil klein genug ist, um sicherzustellen größer ist als die Anzahl der Zustände dieses Automaten Der Haupttrick ist, dass wir uns auf -Übergänge einstellen müssen .)llll|w||w|ϵϵ

Fall 2. . Sei ein p' Level. Zu jeder Stapelgröße , , wir den letzten Push und den ersten Pop . Per Definition sind und . Hier ist eine Illustration dieser Konstruktion. Um das Zeichnen zu vereinfachen, verzichte ich auf die Unterscheidung zwischen Pfadpositionen und Wortpositionen, die wir später vornehmen müssen.lplpi,j,ki,j,kpphhsihsjsihsj lp(h)=max({yj|sy=h})lp(h)=max({yj|sy=h}) fp(h)=min({yj|sy=h})fp(h)=min({yj|sy=h})ilp(h)jilp(h)jjfp(h)kjfp(h)k

Illustration of the construction for case 2. To simplify the drawing, the distinction between the path positions and word positions are ommitted.

Wir sagen, dass der vollständige Zustand einer Stapelgröße das Tripel ist, das gebildet wird durch:hh

  1. der Automatenzustand an Positionlp(h)lp(h)
  2. das oberste Stapelsymbol an Positionlp(h)lp(h)
  3. der Automatenzustand an Positionfp(h)fp(h)

Es gibt mögliche Vollzustände und Stapelgrößen zwischen und , so dass nach dem Pidgeonhole-Prinzip zwei Stapelgrößen mit so dass die Vollzustände bei und sind die gleichen. Wie in Fall 1 definieren wir durch , , und die Positionen der letzten Buchstaben von die an den entsprechenden Positionen in gelesen wurden . Wir wobeippp+1p+1sisisjsjg,hg,hsig<hsjsig<hsjgghh^lp(g)lp(ˆg)^lp(h)lp(ˆh)^fp(h)fp(ˆh)^fp(g)fp(ˆg)wwππw=uvxyzw=uvxyzu=w0^lp(g)u=w0lp(ˆg), , , und .v=w^lp(g)^lp(h)v=wlp(ˆg)lp(ˆh)x=w^lp(h)^fp(h)y=w^fp(h)^fp(g)z=w^fp(g)|w|

Diese Faktorisierung stellt sicher, dass (weil durch unsere Definition von Ebenen).|vxy|pkp

Wir müssen auch zeigen, dass . Beachten Sie dazu, dass wir jedes Mal, wenn wir wiederholen , von demselben Status und derselben Stapelspitze ausgehen und nicht unter unserer aktuellen Position im Stapel springen (andernfalls müssten wir an der aktuellen Position erneut drücken und verletzen) die Maximalität von ), so dass wir den gleichen Pfad in verfolgen und die gleiche Symbolsequenz auf den Stapel legen können. Durch die Maximalität von und die Minimalität von werden wir beim Lesen von nicht unter unsere aktuelle Position im Stapel springen, sodass der im Automaten verfolgte Pfad unabhängig von der Anzahl von gleich ist mal haben wir wiederholtn0,uvnxynzLvlp(g)Alp(h)fp(h)xv. Wenn wir nun so oft wiederholen , wie wir wiederholen , weil wir von demselben Zustand ausgehen, weil wir mit unseren Wiederholungen von dieselbe Symbolsequenz auf den Stapel verschoben haben und weil wir nicht mehr popen, als hat gestapelt durch die Minimierung von können wir dem gleichen Pfad in folgen und die gleiche Symbolsequenz aus dem Stapel ziehen. Daher kann ein Akzeptanzpfad von aus dem Akzeptanzpfad für konstruiert werden .wvvvfp(g)Auvnxynzw

Schließlich haben wir auch , denn wie in Fall 1 können wir , wenn und , einen kürzeren Akzeptanzpfad für erstellen, indem wir und entfernen. .|vy|>1v=ϵy=ϵwπlp(g)lp(h)πfp(h)fp(g)

Wir haben also in beiden Fällen eine ausreichende Faktorisierung und das Ergebnis ist bewiesen.

(Dank geht an Marc Jeanmougin, der mir bei diesem Beweis geholfen hat.)

a3nm
quelle
7

Ja, es ist möglich. Wir könnten den Begriff der Oberflächenkonfigurationen verwenden; Sie wurden vor langer Zeit von Cook vorgestellt. Damit sollte es ziemlich einfach sein, eine Version von pumpfähigem Lemma herauszuholen.

In Bezug auf Oberflächenkonfigurationen sollte fast jedes Papier über LogCFL seine Definition tragen. Hier ist eine aktuelle Arbeit und hier ist eine These

Vielleicht kann jemand, der energischer ist, die Details formulieren!

V Vinay
quelle
Danke für die Antwort! Ja, es ist ziemlich natürlich, die Kombination aus Automatenstatus und oberstem Stapelsymbol zu betrachten. Ich denke immer noch über dieses Problem nach und kann die Details nicht herausfinden ... Hilfe wird geschätzt. :-)
a3nm
3

Der Vollständigkeit halber ein Hinweis auf einen Beweis in diese Richtung.

A.Ehrenfeucht, HJHoogeboom, G.Rozenberg: Koordinierte Paarsysteme. I: Dyck-Wörter und klassisches Pumpen RAIRO, Inf. Théor. Appl. 20, 405-424 (1986)

Abstrakt. Der Begriff eines koordinierten Paarsystems [...] entspricht sehr genau dem Begriff eines Push-Down-Automaten (ist eine andere Formulierung davon). In diesem Artikel untersuchen wir [...] die Möglichkeit, Pump-Eigenschaften von kontextfreien Sprachen durch die Analyse von Berechnungen in cp-Systemen zu erhalten. Dazu analysieren wir die kombinatorische Struktur von Dyck-Wörtern. Die Eigenschaften der von uns untersuchten Dyck-Wörter stammen aus der kombinatorischen Analyse von Berechnungen in cp-Systemen. Wir zeigen, wie diese Entsprechung zum Nachweis des klassischen Pumplemmas verwendet werden kann.

Hendrik Jan
quelle
1

Als er dieses Problem mit Géraud Sénizergues diskutierte, wies er mich auf dieses Papier von Sakarovitch hin, das dieses Ergebnis bereits beweist. Der Beweis scheint auf dieses Papier von Ogden zurück zu gehen.

Verweise:

  • Sakarovitch, Jacques. Sur une propriété d'itération des langages algébriques déterministes. (Französisch. Englische Zusammenfassung). Mathematik. Systems Theory 14 (1981), No. 3, 247–288.
  • William F. Ogden. 1969. Interkalationssätze für Stapelsprachen. In Proceedings des ersten jährlichen ACM-Symposiums zur Computertheorie (STOC '69).
Lamine
quelle