Wenn kontextfrei und regulär ist, ist kontextfrei?

9

Ich bin festgefahren, die nächste Übung zu lösen:

Argumentieren Sie, dass, wenn kontextfrei und regulär ist, (dh der richtige Quotient ) ist kontextfrei.LRL/R={wxRs.twxL}

Ich weiß, dass es einen PDA geben sollte, der akzeptiert, und einen DFA, der akzeptiert . Ich versuche jetzt, diese Automaten zu einem PDA zu kombinieren, der den richtigen Quotienten akzeptiert. Wenn ich das bauen kann, habe ich bewiesen, dass kontextfrei ist. Aber ich bin festgefahren, diesen PDA zu bauen.LRL/R

So weit habe ich es geschafft:

Im kombinierten PDA sind die Zustände ein kartesisches Produkt der Zustände der einzelnen Automaten. Und die Kanten sind die Kanten des DFA, aber nur diejenigen, für die in Zukunft ein Endzustand des ursprünglichen PDA von L erreicht werden kann. Aber ich weiß nicht, wie ich es formell aufschreiben soll.

Dommicentl
quelle
Herzlich willkommen! Wo genau stecken Sie fest, wie gehen Sie vor?
Raphael
1
Hinweis: Überlegen Sie, wie Sie den Nichtdeterminismus am besten nutzen können.
Artem Kaznatcheev
Im kombinierten PDA sind die Zustände ein kartesisches Produkt der Zustände der einzelnen Automaten. Und die Kanten sind die Kanten des DFA, aber nur diejenigen, für die in Zukunft ein Endzustand des ursprünglichen PDA von L erreicht werden kann. Aber ich weiß nicht, wie ich es formal korrigieren soll.
Dommicentl
3
Ich habe Ihren Kommentar in die Frage kopiert. Das ist ein besserer Ort dafür.
Dave Clarke

Antworten:

8

Hier ist ein Hinweis.

Ihr Computer muss zunächst einen Teil eines Wortes aus akzeptieren und dabei das Band verbrauchen. Dann müssen Sie, ohne etwas zu verbrauchen, ein Wort von finden, das die Maschine in einen endgültigen Zustand versetzt. Das ausgewählte Wort aus spielt die Rolle des Eingabeworts für die zweite Hälfte der Berechnung.R R.LRR

Es ist klar, dass Nichtdeterminismus eine Rolle spielen wird, ebenso wie das Produkt zwischen den beiden Maschinen. Der Trick bei der Formalisierung besteht darin, das Produkt so anzupassen, dass die Eingabe von nicht von der Eingabe stammt.R

Dave Clarke
quelle
6

Ich bin mir nicht sicher, was Sie mit dem kartesischen Produkt erreichen. Dadurch werden beide Automaten parallel simuliert, wodurch Sie den Schnittpunkt erhalten. Sie möchten jedoch, dass alle Wörter in identifiziert werden , die ein Suffix von ! Auf einer intuitiven Ebene also.R.LR

Angenommen, unsere Eingabe ist . Offensichtlich können wir nicht alle möglichen Fortsetzungen (für die Mitgliedschaft in ) überprüfen, sondern nur eine begrenzte Anzahl von ihnen. Artems Kommentar ist hier am hilfreichsten; Wir raten, wie das Suffix aussehen wird, und führen beide Automaten darauf aus. R xwΣRx

Lassen und den PDA für und NFA für sind. Konstruieren Sie einen Automaten wie folgt. Simulieren Eingabe . Nach verbraucht wird, Wechsel zu einem modifizierten Schnitt von und , um den Zustand von halten . Entscheiden Sie nun für jeden Übergang nicht deterministisch, welches Symbol in der virtuellen Eingabe als nächstes angezeigt wird. Akzeptiere genau dann, wenn beide Komponenten von gleichzeitig einen Endzustand erreichen, dh wennA R L R A w & Sigma; * A L w A L , R A L A R A L w A L , R w x w x L x RALARLRAwΣALwAL,RALARALwAL,Rwhat eine Fortsetzung , so dass und .xwxLxR

Sie können auch formale Grammatiken verwenden. Sehen Sie, wie Sie in zwei Grammatiken parallel ableiten können? Im Allgemeinen ist nicht klar, wie damit Sie Suffixe im Griff haben. Die Verwendung der Chomsky-Normalform hilft.GL

Angenommen, sowohl als auch sind in Chomsky-Normalform angegeben. Ändern , so dass die am weitesten rechts stehende nicht-Terminal unterscheidbar ist und dessen Startsymbol der neuen Startsymbol machen. Führen Sie für die unterschiedlichen Versionen der Nicht-Terminals neue Regeln ein, die zu einer Grammatik führen, die sich parallel in und ableitet (Nicht-Terminals sind Paare von Nicht-Terminals). Wenn beide Grammatiken mit einem Terminalsymbol übereinstimmen, löschen Sie das zusammengesetzte Nicht-Terminal. Auf diese Weise wird ein Suffix in genau dann gelöscht, wenn es in und in abgeleitet werden und bleibt .GLGRGLGLGRGLGLGRwL/R

Raphael
quelle
Beachten Sie, dass selbst das, was sich in den Spoilerbereichen befindet, weder streng noch formal ist. Bitte lassen Sie mich wissen, wenn Sie weitere Details benötigen (nachdem Sie es selbst ausprobiert haben).
Raphael
6

Ich empfehle, Raphaels Antwort zu verwenden, die viel einfacher zu verstehen ist, aber hier ist eine Alternative, bei der anstelle von Automaten Schließungseigenschaften verwendet werden:

Sei eine Sprache. Wir wollen ein Wort lesen , fragen aber ob in der Sprache ist. Wir wollen also eine neue Sprache aus erstellen, die "gelöscht" hat. Wir können es mit einem Homomorphismus machen, aber es könnte Buchstaben aus entfernen . Lösung: Teilen Sie das Alphabet in zwei Teile und verwenden Sie unterschiedliche Buchstaben für und .LAwLwxLxwwx

Formeller:

1) Erstellen Sie von Wörtern aus , wobei jeder Buchstabe entweder mit 0 oder 1 markiert ist. 2) Schneiden Sie ihn mit der regulären Sprache . Dies erzwingt, dass alle Nullen vor allen Einsen stehen und der zweite Teil von . Die genaue Bedeutung von bleibt dem Leser überlassen. 3) Ersetzen Sie und . Verwendete Schließungseigenschaften: Homomorphes Bild, Vorbild, Schnittpunkt mit regulären Sprachen. Vorteil: Dieser Beweis funktioniert für andere Familien (ersetzen Sie beispielsweise kontextfrei durch regulär). L ( A × 0 ) ( R × 1 ) R × ( a , 0 ) a ( a , 1 ) εL(A×{0,1})L
(A×0)(R×1)R×
(a,0)a(a,1)ε


sdcvvc
quelle
1
Für das, was es wert ist, lässt sich die Automatenkonstruktion auch auf andere Klassen : Zu keinem Zeitpunkt verwenden wir tatsächlich, dass ein PDA ist. AL
Raphael
Guter Punkt.
SDCVVC
1
Technisch gesehen wird eine solche Klasse (wo dieser Beweis funktioniert) als Kegel oder volles Trio bezeichnet .
Hendrik