Informatiker Board | formale Sprachen | Ist die Differenz kontextfrei?

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Ist die Differenz kontextfrei? » Antwort erstellen

» Hallo Gast [Anmelden|Registrieren]

Antwort erstellen

Benutzername:

(du bist nicht eingeloggt!)

Thema:

Nachricht:

HTML ist nicht erlaubt
BBCode ist erlaubt
Smilies sind erlaubt
Bilder sind erlaubt

einfacher Modus erweiterter Modus

aktuellen Tag schließen

alle Tags schließen

Spamschutz:
Text aus Bild eingeben

URLs automatisch umwandeln: fügt automatisch [url] und [/url] in Internet-Adressen ein.
Smilies in diesem Beitrag deaktivieren.
BBCode in diesem Beitrag deaktivieren.
Bilder in diesem Beitrag deaktivieren.
Signatur anzeigen: Soll die im Profil eingestellte Signatur an den Beitrag angehangen werden?
Nachrichtenlänge überprüfen

Die letzten 9 Beiträge
Karlito	Sorry, da fällt mir gerade keins ein. Ich melde mich, wenn mir eins einfällt... VG, Karlito
marie m	Könntest du mir ein Gegenbeispiel geben?
Karlito	Ja genau. VG, Karlito
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?
Karlito	Das müsstest du jetzt eigentlich selbst beantworten können. Versuche es einmal. VG, Karlito
marie m	Ok! Und was ist mit der Differenz M-L?
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
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
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?