Schnitt und Vereinigung von Sprachen

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Schnitt und Vereinigung von Sprachen

Beitrag von JanM » 24. Aug 2010 12:53

Hi,

ich hab mal ne Frage. Wenn ich zwei Sprachen L1 und L2 habe, die nicht den selben Typ in der Chomsky-Hierarchie haben, also zB. ist L1 regulär und L2 kontextsensitiv.
Kann mir jemand eine begründete Antwort geben welchen Typ L1 "geschnitten" L2 und welchen Typ L1 "vereinigt" L2 hat.

Vielen Dank schon mal für die Antwort.

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Schnitt und Vereinigung von Sprachen

Beitrag von bruse » 24. Aug 2010 13:40

Das kann man im Allgemeinen nicht sagen. Ein guter Kandidat ist erstmal die höhere Sprachebene, also bei kontextfrei und regulär dann kontextfrei. Das muss aber nicht stimmen. Zum einen sind die Klassen evtl. nicht unter Durchschnitt abgeschlossen, zum anderen kann die resultierende Sprache natürlich auch zufällig "besser" sein. Der Schnitt des Halteproblems (Typ 0, aber nicht entscheidbar) und seines Komplements (nichtmal Typ 0) ist leer und damit regulär :-)
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: Schnitt und Vereinigung von Sprachen

Beitrag von JanM » 24. Aug 2010 16:31

ok gut, dann habe ich etws speziellere Fragen: von welchem Typ ist die Sprache, die ich bekomme wenn ich ...
a) ... eine reguläre und eine kontextfreie Sprachevereinige
b) ... eine reguläre und eine kontextfreie Spracheschneide
c) ... eine reguläre und eine beliebige Sprache schneide.

Benutzeravatar
igor.a
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 143
Registriert: 28. Sep 2009 16:05

Re: Schnitt und Vereinigung von Sprachen

Beitrag von igor.a » 24. Aug 2010 17:32

zu a) und b) : kontextfrei, siehe http://d120.de/forum/viewtopic.php?f=156&t=20212

Benutzeravatar
JanM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 157
Registriert: 24. Aug 2010 10:58

Re: Schnitt und Vereinigung von Sprachen

Beitrag von JanM » 24. Aug 2010 19:33

Danke. Habs auch gefunden, nachdem ich geschrieben hatte ;) man sollte nicht immer so vorschnell sein

Benutzeravatar
bruse
Kernelcompilierer
Kernelcompilierer
Beiträge: 412
Registriert: 2. Aug 2006 22:42

Re: Schnitt und Vereinigung von Sprachen

Beitrag von bruse » 24. Aug 2010 23:01

a,b wurde bereits beantwortet. c ist i.a. nicht klar.
Un hombre de frente a una ventana
Súper lúcida la mirada
Recorre el paisaje y no,
no es su interior, es luna.

kartzow
Mausschubser
Mausschubser
Beiträge: 55
Registriert: 8. Apr 2010 14:12

Re: Schnitt und Vereinigung von Sprachen

Beitrag von kartzow » 25. Aug 2010 08:19

zu c) na ja nicht klar ist vielleicht nicht ganz umfassend beantwortet, im allgemeinen ist das Resultat eine beliebige Sprache (,die im allgemeinen nicht mal durch eine Grammatik erzeugt werden kann. )

Sei L irgendeine beliebige Sprache ueber \(\Sigma\), und sei M die regulaere Sprache \(\Sigma^*\), dann ist der Schnitt von L und M natuerlich L, d.h. jede Sprache kann als schnitt einer Sprache und einer regulaeren Sprache dargestellt werden!

Antworten

Zurück zu „Archiv“