Informatiker Board | Theoretische Informatik | Komplement der Differenz von Sprachen

Informatiker Board » Themengebiete » Theoretische Informatik » Komplement der Differenz von Sprachen » 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

Smilies: 21 von 33

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 2 Beiträge

NixJava

Zitat:

Die Differenz einer det. kontextfreien Sprache und einer kontextfreien Sprache ist erneut kontextfrei. Nach einem Satz aus der VL ist die Klasse der kontextfreien deterministischen Sprachen unter Komplementbildung abgeschlossen.

Ich sehe u.a. bei den fettgedruckten Hervorhebungen Probleme mit deiner logischen Schlussfolgerung. Die det. kontextfreien Sprachen sind unter dem Komplement abgeschlossen, die kontextfreien Sprachen sind es nicht.

Ich würde $[latex]L_1 \setminus L_2[/latex]$ äquivalent als Schnitt $[latex]\cap[/latex]$ zweier Sprachen ausdrücken und schauen, ob sich nach weiteren mengentheoretischen Umformungen Aussagen bzgl. der Abgeschlossenheit ergeben.

BellaBimba97

Komplement der Differenz von Sprachen

Meine Frage:
Hallo zusammen,

Ich soll mit 2-3 Sätzen begründen, ob folgende Aussage wahr oder falsch ist:
Ist L1 eine deterministische kontextfreie Sprache und L2 eine kontextfreie Sprache, dann ist das Komplement von L1-L2 kontextfrei.

Meine Ideen:
Meine Idee wäre:

Die Differenz einer det. kontextfreien Sprache und einer kontextfreien Sprache ist erneut kontextfrei. Nach einem Satz aus der VL ist die Klasse der kontextfreien deterministischen Sprachen unter Komplementbildung abgeschlossen. Also ist die Aussage wahr.