Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- Ist die Differenz kontextfrei? (http://www.informatikerboard.de/board/thread.php?threadid=1768)

Geschrieben von marie m am 11.01.2014 um 00:51:

  Ist die Differenz kontextfrei?

Hallo!!!

Wenn L eine kontextfreie Sprache ist und M eine reguläre, ist dann die Differenz L-M kontextfrei?


Geschrieben von Karlito am 12.01.2014 um 22:48:

 

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


Geschrieben von Karlito am 13.01.2014 um 00:05:

 

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


Geschrieben von marie m am 13.01.2014 um 01:25:

 

Ok! smile

Und was ist mit der Differenz M-L?


Geschrieben von Karlito am 13.01.2014 um 08:46:

 

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

VG,

Karlito


Geschrieben von marie m am 13.01.2014 um 08:59:

 

[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?


Geschrieben von Karlito am 13.01.2014 um 13:34:

 

Ja genau.

VG,

Karlito


Geschrieben von marie m am 13.01.2014 um 21:48:

 

Könntest du mir ein Gegenbeispiel geben?


Geschrieben von Karlito am 13.01.2014 um 22:10:

 

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

VG,

Karlito


Forensoftware: Burning Board, entwickelt von WoltLab GmbH