Abgeschlossenheit rekursiv aufzählbarer Sprachen |
09.03.2008, 16:16 | Auf diesen Beitrag antworten » |
donvito | Abgeschlossenheit rekursiv aufzählbarer Sprachen Da bei uns sehr klausurwahrscheinlich, frage ich hier mal nach: über welchen Operationen sind rekursiv aufzählbare Sprachen abgeschlossen? Schnitt Man kann eine TM C aus den TMs A und B konstruieren (A akzeptiert Sprache A, B Sprache B). C funktioniert wie folgt:Auf Eingabe w wird zuerst A aufgerufen, dann B. Wenn beide akzeptieren, akzeptiert auch C. Ansonsten lehnt C ab. Komplement Hier kann man nur sagen weder noch. Das Komplement kann sowohl rekursi sein als auch rekursiv-ko-aufzählbar (=nicht rekursiv aufzählbar). Wie schaut das bei den Operationen Stern und Kontakenation aus? Laut Buch sind sie abgeschlossen, nur, wie beweise ich das richtig? |
|
|
09.03.2008, 17:36 | Auf diesen Beitrag antworten » |
Tobias | Hallo, Ja, die ersten beiden Argumente sind richtig. In deiner Liste fehlt vielleicht auch noch "Vereinigung". Aber das ist aich schnell bewiesen: Lasse beide TM parallel laufen (parallel ist wichtig, denn wir haben ja nur semi-Entscheidbarkeit) und akzeptiere, falls eine der beiden TM akzeptiert. Für Konkatenation und Stern konnte ich mir zwar nichts ergoogeln, aber ich denke man kann folgendermaßen argumentieren: Konkatenation: Seien A und B TM, die die Sprachen L(A) und L(B) semi-entscheiden. Sei w ein Wort aus L(A)*L(B). Betrachte für w alle möglichen Zerlegungen . Es gibt nur endlich viele Zerlegungen, da w endlich ist. Für alle Zerlegungen prüfe parallel, ob . Kleensche Hülle (Stern): Da wir das Argument für Konkatenation bereits kennen, können wir hier einfach induktiv vorgehen. Sei A die TM, die L semi-entscheidet. Prüfe also für i = 0, 1, ... im Diagonalverfahren ob . Benutze dabei für i>1: , was durch Induktion auf Konkatenation zurückzuführen ist. Diagnoalverfahren deshalb, weil ein Test für nicht terminieren könnte. Gehe also so vor: Simuliere einen Schritt für den Test , danach zwei Schritte für die Tests usw. |
|
Verwandte Themen
Die Beliebtesten » |
|
Die Größten » |
Die Neuesten » |
|