Contents

Überblick über diese Hilfsmittel für das Arbeiten mit regulären Sprachen und was es zu beachten gibt

Links

Da ich ziemlich schockiert war, was mir in meiner Tätigkeit als Tutor von meinen Übungsgruppenteilnehmern als Pumping Lemma- bzw. Myhill-Nerode-Beweise aufgetischt wurde, habe ich ein kleines Merkblatt zusammengetippt, das diese beiden Beweismethoden kurz erläutert und besonders auf häufige Fehler, die gemacht werden, hinweist.

Sowohl das Pumping Lemma als auch der Satz von Myhill-Nerode sind wichtige Beweismethoden, um die Regularität oder Nichtregularität einer Sprache zu zeigen (und außerdem klassischer Klausurstoff), und nicht schwierig anzuwenden, wenn man darauf achtet, die Beweise gründlich zu führen.

Kommentare sind jederzeit willkommen!

Das Merkblatt (PDF)

07. 12. 2006 - Korrektur #1: Mit dem Pumping Lemma allein lässt sich die Regularität einer Sprache anders als behauptet nicht zeigen.