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.
quelle
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.1⟶ A B. P.1⟶ B A. P.1⟶ a a & egr ; & Sgr;
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.
quelle
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.
quelle