Wie kann man beweisen, dass kontextsensitive Sprachen unter Überschneidung und Ergänzung geschlossen sind?

Dies ist eine Frage aus der Prüfung unseres Kurses "Automaten und formale Sprachen". Es wurde eine Frage gestellt, um zu beweisen oder zu widerlegen, dass jede "relative Komplement" -Operation zwischen zwei kontextsensitiven Sprachen auch eine kontextsensitive Sprache erzeugt.

Aus den kontextsensitiven Schließungseigenschaften Wikipedia und princeton.edu . Ich weiß, dass diese Sprachen unter Schnittmenge und Ergänzung geschlossen sind.

Ich habe zu viel Zeit damit verbracht, den formalen Beweis für diese Aussagen zu finden. Wo / Wie finde ich die Beweise? Oder wie kann ich sie selbst beweisen? Kann mich jemand auf eine Referenz verweisen? Kann hier jemand die Beweise posten?

formal-languages closure-properties context-sensitive Arty
quelle

Ihre Frage ist für diese Site nicht spezifisch genug. Sagen Sie uns, was Sie versucht haben und wo Sie stecken geblieben sind. Das Ziel der Bildung ist es zu lernen, wie man Probleme löst, nicht wie man andere Menschen dazu bringt, Ihre Probleme zu lösen.

Reinierpost

Ich glaube nicht, dass du Recht hast, meine Frage ist sehr streng. Ich habe festgestellt, dass ich keine Referenz finden kann, die einige der LCS-Verschlusseigenschaften belegt. Ich habe nicht darum gebeten, die ursprüngliche Frage zu lösen, da ich die Lösung auch gepostet habe ...

Arty

Ich denke, Sie haben vielleicht Recht, dass die genaue Frage dort nicht beantwortet wird.

Reinierpost

Antworten:

Die erste Schließungseigenschaft, Schließung unter Kreuzung, ist ein DIY-Beweis, wenn Sie das richtige Modell für die kontextsensitiven Sprachen auswählen. Indem Sie sie mit Hilfe von linear begrenzten Automaten definieren, können Sie zwei dieser Automaten nacheinander ausführen, um (nicht deterministisch) die Akzeptanz der Schnittmenge zu testen.

Zweitens ist der Abschluss unter Ergänzung schwierig! Es war ein berühmtes offenes Problem, bis es von Immerman und Szelepcsényi unabhängig gelöst wurde. Es ist ein ziemlich überraschender Beweis, wie man eine Ergänzung für einen nichtdeterministischen Automaten beweist. Die Technik heißt induktives Zählen bezeichnet und funktioniert für größere Familien von Komplexitätsklassen: NSPACE ( $s(n)$ ) = Co-NSPACE ( $s(n)$ ), wobei kontextsensitiv gleich linearem nichtdeterministischem Raum ist .

Hendrik Jan.
quelle

Vielen Dank, jetzt, wenn ich diese Referenz habe, werde ich nach Büchern suchen. Können Sie erklären, was Sie unter "richtigem Modell für die kontextsensitiven Sprachen" verstehen, um sich selbst zu beweisen?

Arty

@arty Wie Sie wissen, kann CSL mit kontextsensitiven Grammatiken oder mit linear begrenzten Automaten definiert werden. Für einige Aufgaben ist die Wahl des Modells entscheidend. Ich mag LBA, weil sie einfach zu "programmieren" sind.

Hendrik Jan

@ Jan war sich einfach nicht sicher, was mit dem Wort "Modell" gemeint ist - jetzt verstehe ich, dass es das Repräsentationsmodell der CSL ist. Nur um Sie zu informieren, es gibt keinen anderen Ort im Web, an dem diese Informationen verfügbar sind. Ich denke, Ihre Eingabe wird vielen Informatikstudenten und Doktoranden (wie mir) helfen, die zusätzliche Kenntnisse

Arty