Informatiker Board | Theoretische Informatik | Kontextfrei Sprache-Abschlusseigenschaften

Informatiker Board » Themengebiete » Theoretische Informatik » Kontextfrei Sprache-Abschlusseigenschaften » 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 10 Beiträge
Karlito	Du verstehst das richtig.Die beiden Sprachen sind gleich. VG, Karlito
marie m	Also sind die zwei Sprachen doch nicht die selben? Oder verstehe ich es falsch?
Karlito	Genau
marie m	Kann von der Sprache $[latex]\{w \in \{a,b\}^{*}: w \neq a^i b^i, i \geq 0\} [/latex]$ das Wort entstehen? Das Wort soll nur nicht die Form oder haben, oder?
Karlito	Oh, sorry, verlesen... Ja, das sind gleiche Sprachen.
marie m	Mit der zweite Sprache meine ich: $[latex] \{w \in \{a,b\}^{}: w \neq a^i b^i, i >=0\} [/latex]$ Bedeutet das nicht das die Anzahl von a nicht die gleiche sein soll wie die Anzahl von b? Das bedeutet nicht auch die Sprache $[latex] \{w \in \{a,b\}^{}: w = a^i b^j, i \neq j \} [/latex]$ ?
Karlito	Hallo, nein! In der ersten Sprache müssen ja i und j unterschiedlich sein und in der zweiten hat die Potenz immer den selben Wert. D.h. in der zweiten Sprache sind ab, aabb, ... enthalten, in der ersten aber eben genau nicht! Aber Achtung! $[latex]L=\{a,b\}^* \setminus \{a^ib^i~\|~i>=0\} [/latex]$ kann nicht verwendet werden, da kontextfreie Sprachen unter Komplement nicht abgeschlossen sind. VG, Karlito
marie m	Ok! Ich habe noch eine Frage... Ist die Sprache {w in {a,b}: w=a^i b^j, i != j} die selbe wie die Sprache {w in {a,b}: w != a^i b^i, i >=0} ?
Karlito	Ich sehe da keinen Weg... Edit: Etwas konkreter: a^jb^i mit i!=j ist eine kontextfreie, aber nicht reguläre Sprache. Da die Beispiele alle regulär sind (bei dem ersten Beispiel ist es nicht eindeutig, da j nicht definiert ist) und reguläre Sprachen unter allen Operationen abgeschlossen sind kann daraus keine kontextfreie Sprache entstehen. VG, Karlito
marie m	Also kann ich keins dieser Beispiele für diese Sprache verwenden ?
Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen.