Informatiker Board | Theoretische Informatik | Paradebeispiel regulär/kontextfrei, folgern

Informatiker Board » Themengebiete » Theoretische Informatik » Paradebeispiel regulär/kontextfrei, folgern » 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 3 Beiträge
Phoney	Ok. Danke für deine Bestätigung und die Tipps für den Nachweis.
Tobias	Ich denke du hast mit beiden Vermutungen Recht. Den Beweis zum ersten Teil kann man m.E. mit dem Satz von Myhill-Nerode recht gut führen. Der Beweis zur nicht-Kontextfreiheit der zweiten Sprache habe ich mit dem Pumping-Lemma für kontextfreie Sprachen nicht hinbekommen (lasse mich aber gerne eines Besseren belehren). Mit der Verallgemeinerung Ogdens-Lemma lässt sich der Beweis jedoch führen.
Phoney	Paradebeispiel regulär/kontextfrei, folgern Hallo ist $[latex]\{a^m b^n : m >= n \}[/latex]$ regulär? Ich kenne das Paradebeispiel $[latex]\{a^n b^n :n\in \mathbb{N} \}[/latex]$ ist nicht regulär, sondern kontextfrei. Ich würde daraus jetzt folgern, daß der Term aus der Aufgabe auch nicht kontextfrei ist, da der Automat für jedes geschriebene a einen Zustand braucht. Also zunächst einmal behaupte ich $[latex]\{a^m b^n : m >= n \}[/latex]$ ist nicht regulär. Stimmts? ist $[latex] \{a^m b^m c^n : m >= n \}[/latex]$ kontextfrei? Auch hier fällt mir sofort das Paradebeispiel ein für kontextsenitive Sprachen $[latex] \{a^m b^m c^m : m \in \mathbb{N} \}[/latex]$ ist kontextsensitiv, aber nicht kontextfrei. Jetzt würde ich von der Form darauf schließen, $[latex] \{a^m b^m c^n : m >= n \}[/latex]$ ist nicht kontextfrei. Könnt ihr mir sagen, ob ich mit meinen Vermutungen richtig liege? Das würde schon mal sehr helfen Danke Phoney