Informatiker Board | Theoretische Informatik | Abgeschlossenheit rekursiv aufzählbarer Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » Abgeschlossenheit rekursiv aufzählbarer Sprachen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Abgeschlossenheit rekursiv aufzählbarer Sprachen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

donvito donvito ist weiblich

Mitglied

Dabei seit: 04.01.2007
Beiträge: 41
Herkunft: Freiburg

Abgeschlossenheit rekursiv aufzählbarer Sprachen

Zitatantwort auf diesen Beitrag erstellen

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?

__________________
Meine Moviebase

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von donvito: 09.03.2008 16:29.

09.03.2008 16:16

Nehmen Sie donvito in Ihre Freundesliste auf

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 $[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.

09.03.2008 17:36

Nehmen Sie Tobias in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Abgeschlossenheit rekursiv aufzählbarer Sprachen