Abgeschlossenheitseigenschaften

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Abgeschlossenheitseigenschaften

Beitrag von patrix »

Hallo zusammen,
ich habe eine Frage bezüglich der Abgeschlossenheitseigenschaften unter Komplement von kontextfreien und regulären Sprachen:
Sei \(L_1\) eine kontextfreie Sprache und \(L_2\) eine reguläre Sprache.
Wären diese beiden Sprachen unter Durchschnitt oder Vereinigung zusammengeführt so wäre doch auch das Komplement dieser neuen Sprache \(L\) abgeschlossen da es entscheidbar wäre oder?

Viele Grüße Patrick

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: Abgeschlossenheitseigenschaften

Beitrag von AlexPi11 »

Durchschnitt und Vereinigung der beiden Sprachen \(L_{1}\) und \(L_{2}\) ergeben kontextfreie Sprachen. Kontextfreie Sprachen sind bezüglich der Komplementbildung nicht abgeschlossen. Die Entscheidbarkeit (des Wortproblems?) ist dabei eigentlich egal.

patrix
Mausschubser
Mausschubser
Beiträge: 71
Registriert: 16. Nov 2009 17:10

Re: Abgeschlossenheitseigenschaften

Beitrag von patrix »

Alles klar, Danke

pabloarias
Erstie
Erstie
Beiträge: 15
Registriert: 1. Okt 2009 09:05

Re: Abgeschlossenheitseigenschaften

Beitrag von pabloarias »

Hallo Alex,

wieso behauptest du, dass der Durchschnitt zwischen einer regulaeren und einer kontextfreier Sprache eine kontextfreie Sprache ergibt?

Wir haben doch in der Vorlesug gesehen, dass es nicht immer einen PDA gibt, der den Durchschnitt zweier kontextfreien Sprachen erkennt, siehe Skript seite 55 Korollar 3.311

Kontextfreie Sprachen sind unter Durchschnitt nicht abgeschlossen.

Benutzeravatar
AlexPi11
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 154
Registriert: 18. Apr 2009 15:32

Re: Abgeschlossenheitseigenschaften

Beitrag von AlexPi11 »

Für den Fall regulär-kontextfrei habe ich mal gegoogelt, nachdem Wikipedia meinte, dass der Durschnitt kontextfrei wäre. Beweis-skizze
Im Skript habe ich jetzt auch nichts auf die Schnelle gefunden. Aber gut; auch ohne diesen Satz kommt man ja auf einen Widerspruch.

nicolas
Windoof-User
Windoof-User
Beiträge: 37
Registriert: 29. Jan 2010 12:56

Re: Abgeschlossenheitseigenschaften

Beitrag von nicolas »

Alternativ: Siehe Übung 6, G2b), wo es darum geht, einen PDA zu konstruieren, der den Schnitt einer kontextfreien und einer regulären Sprache erkennt. Zumindestens in den Übungen war so eine Konstruktion also schon Thema.

Antworten

Zurück zu „Archiv“