Sprache Entscheidbar < Formale Sprachen < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 17:31 Do 08.09.2011 | | Autor: | Harris |
| Aufgabe | Es seien [mm] $\Sigma$ [/mm] ein Alphabet, [mm] L_1 [/mm] und [mm] L_2 [/mm] zwei Sprachen über [mm] $\Sigma$. \epsilon [/mm] bezeichne das leere Wort. Zeigen oder widerlegen Sie:
Sind sowohl [mm] L_1 [/mm] als auch [mm] L_2 [/mm] mit einer deterministischen Turing-Maschine mit polynomieller Zeitkomplexität entscheidbar, so gilt dies auch für [mm] L_1\backslash L_2. [/mm] |
Hallo!
Ich habe ein Problem mit dieser Aufgabe.
Eine (eventuell falsche) Lösung widerlegt:
[mm] L_1\backslash L_2 [/mm] = [mm] L_1\cap \overline{L_2}
[/mm]
Durch die polynomielle Laufzeit ist nur ausgesagt, dass die Sprachen vom Typ 0 sind. Hierbei ist der Schnitt zwar eine abgeschlossene Operation, die Komplementbildung aber nicht. D. h. [mm] L_1\backslash L_2 [/mm] ist nicht unbedingt von Typ 0 und damit auch nicht entscheidbar.
Wir sind aber der Meinung:
Wir sichern erstmal das Wort. Wir lassen das erste Turingprogramm laufen und gelangen (wegen der Entscheidbarkeit terminiert es) in einen akzeptierenden oder einen nicht akzeptierenden Zustand. Terminiert sie in einem nicht akzeptierenden Zustand, so sind wir fertig.
Das zweite Turingprogramm starte in dem akzeptierenden Zustand des ersten Turingprogrammes. Da auch die zweite Sprache entscheidbar ist, terminiert auch dieses zweite Turingprogramm. Vertauschen wir die akzeptierenden und nicht akzeptierenden Zustände des zweiten Turingprogrammes, so entscheiden wir genau die oben genannte Sprache.
Die Polynomielle Laufzeit ist trivial.
Welche der beiden "Lösungen" ist falsch?
Viele Grüße,
Harris
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:20 Sa 10.09.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
