 Ist die Differenz kontextfrei? |
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
 |
|
| Ist die Differenz kontextfrei? |
     |
Hallo!!!
Wenn L eine kontextfreie Sprache ist und M eine reguläre, ist dann die Differenz L-M kontextfrei?
|
|
11.01.2014 00:51 |
|
|
Karlito 
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
|
12.01.2014 22:48 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
ich habe noch mal überlegt, es ist wohl möglich:
![[latex] L\setminus M \equiv L \cap \overline{M}[/latex]](http://www.matheboard.de/latex2png/latex2png.php? L\setminus M \equiv L \cap \overline{M}) .
Da M regulär und damit unter Komplement abgeschlossen ist, gilt die Behauptung.
Klar?
VG,
Karlito
|
|
|
13.01.2014 00:05 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Ok! 
Und was ist mit der Differenz M-L?
|
|
|
13.01.2014 01:25 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Das müsstest du jetzt eigentlich selbst beantworten können. Versuche es einmal.
VG,
Karlito
|
|
|
13.01.2014 08:46 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
![[latex] M-L = M \cap L' [/latex]](http://www.matheboard.de/latex2png/latex2png.php? M-L = M \cap L' ) . Da die Kontextfreien Sprachen nicht unter Komplement abgeschlossen sind, ist diese Differenz nicht kontextfrei. Kann man das so sagen?
|
|
|
13.01.2014 08:59 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
|
|
13.01.2014 13:34 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Könntest du mir ein Gegenbeispiel geben?
|
|
|
13.01.2014 21:48 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Sorry, da fällt mir gerade keins ein. Ich melde mich, wenn mir eins einfällt...
VG,
Karlito
|
|
|
13.01.2014 22:10 |
|
|
|
