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

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

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Paradebeispiel regulär/kontextfrei, folgern

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Paradebeispiel regulär/kontextfrei, folgern

Zitatantwort auf diesen Beitrag erstellen

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 13:01

Nehmen Sie Phoney in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

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 18:22

Nehmen Sie Tobias in Ihre Freundesliste auf

Phoney
Jungspund

Dabei seit: 13.12.2006
Beiträge: 20

Ok. Danke für deine Bestätigung und die Tipps für den Nachweis. Mit Zunge

13.01.2008 19:19

Baumstruktur | Brettstruktur

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