Entscheidbarkeit Komplexität < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:20 So 07.12.2008 | | Autor: | Moe007 |
| Aufgabe | a) Sind [mm] L_{1} [/mm] und [mm] L_{2} [/mm] entscheidbar, so ist auch [mm] L_{1} \circ L_{2} [/mm] = [mm] {w_{1}w_{2} \in sigma^{*} | w_{1} \in L_{1}, w_{2} \in L_{2}} [/mm] entscheidbar.
b)Sind [mm] L_{1} [/mm] und [mm] L_{2} [/mm] jeweils in der KOmplexitätsklasse P entscheidbar, so gilt dies auch für [mm] L_{1} [/mm] \ [mm] L_{2}. [/mm] |
Hallo.
Ich habe versucht, die obigen Aufgabenstellungen zu lösen. Komme aber auf keine richtige Lösung.
Falls mir hier jemand helfen kann, wäre ich sehr dankbar!
zu a) Ich bin hier davon ausgegangen, dass [mm] L_{1} [/mm] und [mm] L_{2} [/mm] jeweils Sprachen vom Typ 1 sind. Diese sind bekanntermaßen unter Produktbildung abgeschlossen. Kann ich daraus schon folgern, dass dann das Produkt von [mm] L_{1} \circ L_{2} [/mm] entscheidbar ist?
zu b) Ich weiß, dass [mm] L_{1} \in [/mm] P [mm] \gdw \overline{L_{1}} \in [/mm] P. Das gleiche gilt für [mm] L_{2}, [/mm] d.h. [mm] L_{2} \in [/mm] P [mm] \gdw \overline{L_{2}} \in [/mm] P
Dann gilt ja: [mm] L_{1}\L_{2} [/mm] = [mm] L_{1} \cap \overline{L_{2}}
[/mm]
Nun meine Frage: ISt der Schnitt dann auch in P, wenn beide Sprachen jeweils in P sind?
Vielen Dank!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:40 Mo 08.12.2008 | | Autor: | bazzzty |
> zu a) Ich bin hier davon ausgegangen, dass [mm]L_{1}[/mm] und [mm]L_{2}[/mm]
> jeweils Sprachen vom Typ 1 sind. Diese sind bekanntermaßen
> unter Produktbildung abgeschlossen. Kann ich daraus schon
> folgern, dass dann das Produkt von [mm]L_{1} \circ L_{2}[/mm]
> entscheidbar ist?
Versuch doch mal konstruktiv zu argumentieren. Du hast eine Maschine, die Wörter aus [mm] L_1 [/mm] entscheidet, und eine, die Wörter aus [mm] L_2 [/mm] entscheidet. Jetzt gebe ich Dir ein Wort. Wie stellst Du fest, ob es sich zerlegen läßt?
> zu b) Ich weiß, dass [mm]L_{1} \in[/mm] P [mm]\gdw \overline{L_{1}} \in[/mm]
> P. Das gleiche gilt für [mm]L_{2},[/mm] d.h. [mm]L_{2} \in[/mm] P [mm]\gdw \overline{L_{2}} \in[/mm]
> P
> Dann gilt ja: [mm]L_{1}\L_{2}[/mm] = [mm]L_{1} \cap \overline{L_{2}}[/mm]
Hier das gleiche: Versuche, das Problem zu lösen, statt zu zeigen, daß es lösbar ist. Du hast zwei Algorithmen, die in Polynomialzeit die beiden Sprachen entscheiden. Wie entscheidest Du [mm]L_{1}\L_{2}[/mm] in Polynomialzeit?
> Nun meine Frage: ISt der Schnitt dann auch in P, wenn beide
> Sprachen jeweils in P sind?
Ja. Aber da kommst Du auch selbst drauf, wenn Du nicht nur in Formeln denkst, sondern in Problemen und Lösungen!
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:55 Di 09.12.2008 | | Autor: | Moe007 |
hi,
also ich hab jetzt versucht, die a) folgendermaßen zu lösen, und zwar anhand der Definitionen von Entscheidbarkeit:
Da [mm] L_{1} [/mm] entscheidbar ist, ist die charakt. Funktion [mm] \mu_{L1}: \summe{*} \to [/mm] {0,1} berechenbar.
[mm] \mu_{L1}(w_{1})= [/mm] 1 falls [mm] w_{1} \in L_{1} [/mm] und 0 falls [mm] w_{1} \not\in L_{1}
[/mm]
Analog für [mm] L_{2}, [/mm] da auch diese entscheidbar ist.
Nach Definition ist nun [mm] w=w_{1}w_{2} \in L_{1}\circ L_{2}, [/mm] wenn [mm] w_{1} \in L_{1} [/mm] und [mm] w_{2} \in L_{2}
[/mm]
Dann hab ich versucht einen Entscheidungsalgorithmus M= [mm] M_{1} \circ M_{2} [/mm] für [mm] L_{1}\circ L_{2} [/mm] anzugeben, bei dem bei [mm] M_{1} [/mm] überprüft wird, ob [mm] w_{1} \in L_{1} [/mm] und bei [mm] M_{2} [/mm] ob [mm] w_{2} \in L_{2} [/mm] ist. Wenn am Ende 1 herauskommt, liegt w in [mm] L_{1}\circ L_{2}, [/mm] sonst 0.
INPUT(w);
FOR s,t := 1,2,3,... DO
IF [mm] M_{1} [/mm] bei Eingabe [mm] w_{1} [/mm] stoppt in s Schritten
AND IF [mm] M_{2} [/mm] bei Eingabe [mm] w_{2} [/mm] stoppt in t Schritten
THEN OUTPUT (1) END;
ELSE OUTPUT (0) END;
END
Deshalb ist die Verknüpfung von 2 entscheidbaren Sprachen wieder entscheidbar. Kann das so machen?
Viele Grüße,
Moe
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 13:36 Di 09.12.2008 | | Autor: | bazzzty |
Du machst es Dir noch ein bißchen zu kompliziert. Wenn [mm]w\in L_1\circ L_2[/mm], dann gibt es eine Zerlegung. Du hast zwei Maschinen, die [mm] M_1 [/mm] bzw [mm] M_2 [/mm] entscheiden, und jetzt ist der Entscheidungsalgorithmus folgender:
Für alle Zerlegungen von [mm] w_{} [/mm] in [mm] w_1 [/mm] und [mm] w_2, [/mm] teste, ob [mm] w_1\in L_1 [/mm] und [mm] w_2\in L_2. [/mm] Ist das für eine Zerlegung der Fall, dann ist [mm] w\in [/mm] L, sonst nicht.
|
|
|
|
