Klausur 2008 - Aufgabe 4

n!ghtwaX
Neuling
Neuling
Beiträge: 4
Registriert: 14. Okt 2008 11:39

Klausur 2008 - Aufgabe 4

Beitrag von n!ghtwaX »

Hallo zusammen,

Ich hab noch so ein paar Probleme mit dieser Aufgabe, da die Argumentationen sehr schwierig sind.

a) Jede kontextfreie Sprache hat ein aufzählbares Komplement.

Hier könnte man ja mit den Abschlusseigenschaften argumentieren. Das Komplement ist ja unter Typ 2 und Typ 0 nicht abgeschlossen. Doch führt dieser Weg wirklich zur Lösung.

b) Sind L1 und L2 kontextfreie Sprachen, dann ist auch L1/L2 kontextfrei.

Man könnte ja L1 und L2 gleichsetzen und dann L2 von L1 abziehen und dann hätte man eine leere Menge und somit wäre es eine reguläre Sprache, also auch kontextfrei. Aber gibt es auch Gegenbeispiele oder sollte man hier ganz anders argumentieren.

c) Jede Sprache mit endlichem Komplement ist regulär.

Eine endliche Sprache ist eine reguläre Sprache und das Komplement ist unter regulären Sprachen abgeschlossen. Ist dies als Argumentation ausreichend oder nicht?

d) Ist L1 regulär und L2 beliebig, dann ist L= {x element Sigma * : es existiert ein y element L2, so dass xy element L1}.

Hier fehlt mir leider jeglicher Ansatz.

Wäre super, wenn ihr da ein paar Ansätze hättet :)

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: Klausur 2008 - Aufgabe 4

Beitrag von linn »

schau dir mal die lösung für Übung 8 an ;)

n!ghtwaX
Neuling
Neuling
Beiträge: 4
Registriert: 14. Okt 2008 11:39

Re: Klausur 2008 - Aufgabe 4

Beitrag von n!ghtwaX »

Oh man...Augen müsste man im Kopf haben :P Ist halt schlecht wenn man nur bis Übung 7 macht und die 8 auslässt :)
Danke dir!

Antworten

Zurück zu „Archiv“