Paradebeispiel regulär/kontextfrei, folgern

13.01.2008, 13:01	Auf diesen Beitrag antworten »
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


13.01.2008, 18:22	Auf diesen Beitrag antworten »
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.
13.01.2008, 19:19	Auf diesen Beitrag antworten »
Phoney	Ok. Danke für deine Bestätigung und die Tipps für den Nachweis.

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »