Kontextfreie Sprachen, die unter Umkehrung geschlossen wurden

8

Diese Woche haben wir im Unterricht etwas über die CFLs und ihre Verschlusseigenschaften gelernt. Ich habe Beweise für Vereinigung, Überschneidung und Kompliment gesehen, aber für die Umkehrung sagte mein Dozent nur, dass es geschlossen ist. Ich wollte den Beweis sehen, also habe ich in den letzten Tagen gesucht, aber alles, was ich gefunden habe, ist, dass die meisten Leute nur sagen, dass es ausreicht, die Produktionen umzukehren, um es zu beweisen. Diejenigen, die etwas formeller vorgehen, geben einfach an, dass es einen einfachen induktiven Beweis gibt, den Sie geben können. Kann mir jemand weitere Informationen / Hinweise zum induktiven Beweis geben? Versuchen Sie, wie ich könnte, ich kann es nicht finden.

Sam Hooper
quelle

Antworten:

11

Ihre Quellen haben Recht, und ich fürchte, es gibt nur wenig hinzuzufügen, außer Formalismus. Ich bezeichne die reverse (Spiegel) der String - w von wR .

Wenn eine Grammatik, lassen seine umgekehrt sein, so dass für die Produktion in haben wir in .H A w G A w R H.GHAwGAwRH

Dann durch Induktion zeigen wir , dass iff .A H w R.AGwEINH.wR.

  • ( Basis ) In Schritten Null haben wir iff .A 0 H A.EING0EINEINH.0EIN
  • ( Induktion ) Unter der Annahme von iff wir jede Produktion in (und umgekehrt in ) und und , wobei tatsächlich die Umkehrung von .EINGw1B.w2EINH.w2R.B.w1R.B.uGH.EINGw1uw2EINH.w2R.uR.w1R.w2R.uR.w1R.w1uw2

Dies ist ein sehr kondensierter Beweis, enthält aber alle notwendigen Zutaten. Wiederum ist eine Ableitung der umgekehrten Grammatik die Umkehrung der ursprünglichen. Dies wird besonders deutlich, wenn man sich die beiden Ableitungsbäume ansieht.

Hendrik Jan.
quelle
Gilt dies für eine deterministische kontextfreie Sprache?
Akashchandrakar
@aksam Deterministische CFL werden bei Umkehrung nicht geschlossen. Beachten Sie, dass der Determinismus für CFL normalerweise mit Pushdown-Automaten und nicht mit Grammatiken definiert wird.
Hendrik
7

Es gibt eine andere Möglichkeit, dieses Problem zu betrachten.

Bedenken Sie, dass die Sprache eine CFL ist. Dies bedeutet, dass es eine Grammatik G = { N , , P , S } gibt , die die CFL erfüllt. Wir können davon ausgehen, dass dies in Chomsky-Normalform vorliegt.L.G={N.,,P.,S.}}

Wenn Teil der Sprache ist, ist trivialerweise auch Teil der Sprache. Ersetzen Sie es nun für jede Produktion der Form durch und für die Produktionen der Form , wobei , gleich.ϵϵR.P.1EINB.P.1B.EINP.1einein

Aus dem Analysebaum der abgeleiteten Zeichenfolge ist leicht ersichtlich, dass die abgeleitete Sprache genau die Umkehrung der ursprünglichen Sprache ist, da die Konstruktion den ursprünglichen Analysebaum widerspiegelt.

Ameet Deshpande
quelle
Ich denke nicht, dass dies "ein anderer Weg" ist: Es ist genau der gleiche Weg, der anders formuliert ist (und tatsächlich, glaube ich, leichter zu befolgen). Der Teil, in dem Sie sagen "es ist leicht zu sehen", ist der Teil, in dem die Induktion eintritt. Wie auch immer, +1, da diese Antwort definitiv hilfreich ist.
David Richerby
4

Erst einmal. CFLs werden nicht unter Schnittmenge oder Komplement (oder Differenz für diese Angelegenheit) geschlossen. Sie werden unter Union, Verkettung, Kleene-Sternschluss, Substitution, Homomorphismus, inversem Homomorphismus und Umkehrung geschlossen. HINWEIS: Die beiden Homomorphismen werden normalerweise nicht in einem Einführungskurs in die Computertheorie behandelt.

Um die Umkehrung zu beweisen, sei L eine CFL mit der Grammatik G = (V, T, P, S). Sei L R die Umkehrung von L, so dass die Grammatik G R = (V, T, P R , S) ist. Das heißt, jede Produktion umkehren.

Ex. P -> AB würde P -> BA werden

Da G R ein CFG ist, ist L (G R ) eine CFL.

Ahaywood
quelle
Willkommen auf der Seite! Ich bin erstaunt, dass niemand zuvor bemerkt hat, dass die Frage fälschlicherweise behauptet, dass CFLs unter Schnittmenge und Ergänzung geschlossen sind.
David Richerby