Informatiker Board | Druckvorschau: Abgeschlossenheit rekursiv aufzählbarer Sprachen

Geschrieben von donvito am 09.03.2008 um 16:16:

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?

Geschrieben von Tobias am 09.03.2008 um 17:36:

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 $[latex]w = uv, \; 0 \leq |u|, |v| \leq |w|[/latex]$ . Es gibt nur endlich viele Zerlegungen, da w endlich ist. Für alle Zerlegungen prüfe parallel, ob $[latex]u \in L(A) \; \wedge \; v \in L(B)[/latex]$ .

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.
$[latex]w \in L^\ast \iff w = \varepsilon \vee w \in L \vee w \in L^2 \vee \ldots[/latex]$
Prüfe also für i = 0, 1, ... im Diagonalverfahren ob $[latex]w \in L^i[/latex]$ .
Benutze dabei für i>1: $[latex]w \in L^i \iff w \in L\cdot L^{i-1}[/latex]$ , was durch Induktion auf Konkatenation zurückzuführen ist.
Diagnoalverfahren deshalb, weil ein Test für [latex]L^i[/latex]

nicht terminieren könnte. Gehe also so vor: Simuliere einen Schritt für den Test $[latex]w \in L^1[/latex]$ , danach zwei Schritte für die Tests $[latex]w \in L^1, \; w \in L^2[/latex]$ usw.