Informatiker Board | Druckvorschau: Paradebeispiel regulär/kontextfrei, folgern

Geschrieben von Phoney am 13.01.2008 um 13:01:

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

Geschrieben von Tobias am 13.01.2008 um 18:22:

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.