Klausur Herbst 2002 - Aufgabe I-2

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Klausur Herbst 2002 - Aufgabe I-2
Hallo,

wie zeige, dass L_1 - L_2 entscheidbar ist, wenn L_1 und L_2 entscheidbar sind?

Danke!
bo


Da hätte ich jetzt so argumentiert:

Unter entscheidbar verstehe ich, dass entschieden werden kann, ob ein Wort in der Sprache liegt oder nicht. Das Wort Problem ist für alle Sprachen größer gleich kontextsenstiv entscheidbar. L1 - L2 entspricht L1 ∩ nicht L2. Kontextsensitive Sprachen sind über Schnitt und Komplement abgeschlossen. Also ist das Ergebnis von L1-L2 wieder mindestens kontextsensitiv und somit entscheidbar.


Ich weiß nicht, ob man entscheidbar in diesem Fall einfach auf das Wortproblem reduzieren kann. Wenn man es kann, ist dein Ansatz gut.
Es gibt aber noch andere Probleme im Zusammenhang mit Entscheidbarkeit (siehe Schöning S.90)

Vielleicht muss man hier mit dem Satz argumentieren, „Eine Sprache ist entscheidbar genau dann wenn sowohl A als auch nichtA semi-entscheidbar sin“ (Schöning S.123)
Leider habe ich keinen Plan, wie man das macht…


Dann kannst es aber doch genauso argumentieren. L1 und nicht L1 ist semientscheidbar und L2 und nicht L2 ist semientscheidbar. Also muss auch der Schnitt wieder Semientscheidbar sein. Somit also auch die Differenzmenge.


Ich finde die Idee mit den Abschlusseigenschaften sehr gut.
Aber wenn man über Entscheidbarkeit argumentieren möchte, dann bietet sich doch die charakteristische Funktion an. Ist eine Menge entscheidbar so existiert eine berechenbare charakteristische Funktion die 1 ergibt für ein Argument x aus M und 0 sonst. Existieren für beide Menge solche Funktionen so kann man die charakteristische Funktion für die neue Menge angeben als:
ChNeu(x) = Ch1(x) * (1 - Ch2(x) )
und die ist offensichtlich wieder berechenbar, da Ch1 und Ch2 berechenbar sind
Was meint ihr?


Ich hatte mit meinem Post in etwa das gleiche gemeint, nur irgendwie bisschen doof formuliert. An die char. Funktion hatte ich nur dabei irgendwie nicht gedacht.


Hab mich gerade dazu durchgerungen den Schöning doch noch zu lesen: Da steht auf Seite 19 es gibt entscheidbare Sprachen die nicht kontextsensitiv sind. Damit wäre die Methode die kontextsensitiven Abschlusseigenschaften auszunutzen falsch.


Ok, hast gewonnen. Man sollte nicht davon ausgehen, wenn nicht alle Typ 0 Sprachen entscheidbar sind, dass dann jede Typ 0 Sprache unentscheidbar ist. Aber wenn ich einen Automaten bauen kann, der sagt, das L1 wahr ist oder nicht und L2 wahr ist oder nicht, dann kann der auch sagen ob L1 und nicht L2 wahr ist. Was wieder auf die Idee mit der char. Funktion hinausläuft.