Sprachen-Beweis < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:26 Do 30.05.2013 | | Autor: | bandchef |
| Aufgabe | Sei L eine beliebige Sprache. Zeigen Sie folgende Aussage:
L ist entscheidbar [mm] $\Leftrightarrow$ [/mm] $L$ und [mm] $\overline{L}$ [/mm] sind rekursiv aufzählbar |
Hi Leute!
Also ich hab mir das so gedacht:
rekursiv = entscheidbar und rekursiv aufzählbar = semi-entscheidbar
Eine TM entscheidet bzw. die Sprache ist entscheidbar, wenn die TM für alle Wörter akzeptiert die in L liegen aber bei Wörtern hält die nicht L liegen. Sprich die TM hält, wenn ein Wort kommt, das nicht in L liegt.
Semi-entscheidbar ist eine Sprache dann wenn die TM bei Wörter die nicht in L liegen auch nicht hält.
Wie muss ich das aber nun in einen Beweis verwenden?
|
|
| |
|
Hallo bandchef,
ich weiß ja nicht, auf welcher Ebene ihr den Beweis machen sollt. Da Du ja hier den Ansatz über die Maschinenebene gewählt hast, ein paar kleine Anregungen dazu:
Wie könnte man Turingmaschinen entwerfen, die aus den gegebenen TM die gewünschten Ergebnisse liefert (d.h. wenn man die TM für ein entscheidbares L hat, wie müsste man diese "abändern" / simulieren, dass daraus r.a. für L und das Komplement folgt). Umgekehrt ebenso.
Gruß
Anna
|
|
|
|
