Deterministisch kontextfreien Sprachen | Schnitt

[Dit_]

Hallo
bräuchte Hilfe bei follgendem Problem.

Ich muss beweisen dass zwei deterministisch kontextfreien Sprachen unter Schnitt nicht abgeschlossen sind.

Also, wenn ich zwei solche Sprachen habe, L1 und L2, so entsteht unter Schnitt eine neue Sprache L3. Diese enthält die Wörter die gleichzeitig in L1 und in L2 zu finden sind.. (soweit richtig? )

Weiso ist dann diese neue Sprache L3 nicht mehr deterministisch kontextfrei ? Irgendwie verstehe ich das nicht so ganz :shock:

kann mir jemand Helfen ?

Danke schon mal.

 

[Dit_]

keiner weiss bescheid ?

 

[Sonecc]

Klingt klassich nach Wiederspruchsbeweis...
Überlege dir zwei Sprachen, die die Bedingungen erfüllen und bilde dann den Durchschnitt miteinander.
Prüfe dann alle Bedingungen und Eigenschaften der Definition durch und wenn eines davon nicht zutrifft, hast du die Aussage bewiesen.

Du beginnst also mit:

Annahme: Der Schnitt zweier deterministisch kontextfreier Sprachen ist wieder eine deterministisch kontextfreie Sprache.
Beweis:
Sei LR1 eine DKS definiert durch ...
Sei weiter LR2 eine DKS definiert durch ...
Sei LR3 definiert als die Schnittmenge von LR1 und LR2

Dann gilt für LK3:

Nun gehst du die einzelnen Definition von DKS durch.
Triffst du auf eine, die nicht zutrifft, hast du gewonnen und hast damit deine anfängliche Annahme widerlegt. Damit kann nur noch das Gegenteil stimmen.
Die Aussage ist damit dann bewiesen.

Da ich mich mit DKS nicht auskenne, kann ich dir da leider nicht helfen