Ist die Differenz kontextfrei?

Neue Frage »

Auf diesen Beitrag antworten »
marie m Ist die Differenz kontextfrei?

Hallo!!!

Wenn L eine kontextfreie Sprache ist und M eine reguläre, ist dann die Differenz L-M kontextfrei?
 
Auf diesen Beitrag antworten »
Karlito

Hallo,

intuitiv würde ich erstmal sagen, dass die Behauptung nicht stimmt, da Kontextfreie Sprachen unter komplement nicht abgeschlossen sind und reguläre Sprachen auch kontextfrei sind. Müsste man nur noch ein Gegenbeispiel finden...

VG,

Karlito
Auf diesen Beitrag antworten »
Karlito

Hallo,

ich habe noch mal überlegt, es ist wohl möglich:
[latex] L\setminus M  \equiv L \cap \overline{M}[/latex].

Da M regulär und damit unter Komplement abgeschlossen ist, gilt die Behauptung.

Klar?

VG,

Karlito
Auf diesen Beitrag antworten »
marie m

Ok! smile

Und was ist mit der Differenz M-L?
 
Auf diesen Beitrag antworten »
Karlito

Das müsstest du jetzt eigentlich selbst beantworten können. Versuche es einmal.

VG,

Karlito
Auf diesen Beitrag antworten »
marie m

[latex] M-L = M \cap L' [/latex] . Da die Kontextfreien Sprachen nicht unter Komplement abgeschlossen sind, ist diese Differenz nicht kontextfrei. Kann man das so sagen?
Auf diesen Beitrag antworten »
Karlito

Ja genau.

VG,

Karlito
Auf diesen Beitrag antworten »
marie m

Könntest du mir ein Gegenbeispiel geben?
Auf diesen Beitrag antworten »
Karlito

Sorry, da fällt mir gerade keins ein. Ich melde mich, wenn mir eins einfällt...

VG,

Karlito
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »