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.
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.
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.
quelle
Antworten:
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.L R R
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
quelle
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.L R
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∈Σ∗ R x
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
quelle
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:
Formeller:
quelle