Ist die Differenz kontextfrei? |
11.01.2014, 00:51 | 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? |
|
|
12.01.2014, 22:48 | 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 |
13.01.2014, 00:05 | Auf diesen Beitrag antworten » |
Karlito | Hallo, ich habe noch mal überlegt, es ist wohl möglich: . Da M regulär und damit unter Komplement abgeschlossen ist, gilt die Behauptung. Klar? VG, Karlito |
13.01.2014, 01:25 | Auf diesen Beitrag antworten » |
marie m | Ok! Und was ist mit der Differenz M-L? |
Anzeige | |
|
|
13.01.2014, 08:46 | Auf diesen Beitrag antworten » |
Karlito | Das müsstest du jetzt eigentlich selbst beantworten können. Versuche es einmal. VG, Karlito |
13.01.2014, 08:59 | Auf diesen Beitrag antworten » |
marie m | . Da die Kontextfreien Sprachen nicht unter Komplement abgeschlossen sind, ist diese Differenz nicht kontextfrei. Kann man das so sagen? |
13.01.2014, 13:34 | Auf diesen Beitrag antworten » |
Karlito | Ja genau. VG, Karlito |
13.01.2014, 21:48 | Auf diesen Beitrag antworten » |
marie m | Könntest du mir ein Gegenbeispiel geben? |
13.01.2014, 22:10 | Auf diesen Beitrag antworten » |
Karlito | Sorry, da fällt mir gerade keins ein. Ich melde mich, wenn mir eins einfällt... VG, Karlito |
|