Abgeschlossenheit rekursiv aufzählbarer Sprachen |
donvito
Mitglied
Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg
|
|
|
09.03.2008 16:16 |
|
|
Tobias
Routinier
Dabei seit: 18.09.2006
Beiträge: 324
|
|
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.
|
|
09.03.2008 17:36 |
|
|
|