Senior Sanchez
2009-02-19, 13:08:08
Hi,
Ich lerne gerade für die theoretische Informatik Klausur am Montag und bin gerade auf eine Situation gestoßen, die ich nicht ganz verstehe.
Es geht um reguläre Sprachen, also solche Sprachen die mit regulären Ausdrücken oder endlichen Automaten beschreiben lassen.
Nun lese ich hier im Buch, dass die folgende Sprache regulär ist...
L = {w element {0,1}* | |w|1 <= 2}
Es handelt sich also um die Sprache, die alle Wörter enthält, deren Wörter höchstens zwei Einsen enthalten.
Ich kann dafür ja ohne Probleme einen endlichen Automaten oder regulären Ausdruck konstruieren, der das nachweist und hätte somit gezeigt, dass sie regulär ist.
Allerdings müsste dafür ja auch das Pumping Lemma gelten, dass bekanntlich besagt, dass es für eine reguläre Sprache ein n>=1 gibt, sodass für alle Wörter der Länge >= n eine Zerlegung in w=xyz existiert ( |xy| <= n, y nicht leer). Ferner muss dann für jedes i>=0 das Wort xy^iz wieder in der Sprache liegen, was beim Verfielfältigen von Einsen ja nicht sein würde.
... ach verdammt, jetzt ist mir mein Denkfehler gerade beim Schreiben aufgefallen. *g* Es muss ja nur eine Zerlegung gelten und sobald das Wort mindestens die Länge 3 hat, kann ich das y als die 0 auffassen, was sich ja beliebig aufpumpen lässt.
Ich lass den Thread trotzdem mal hier, falls ich noch mal Fragen habe oder es noch einmal nachlesen will.
Ich lerne gerade für die theoretische Informatik Klausur am Montag und bin gerade auf eine Situation gestoßen, die ich nicht ganz verstehe.
Es geht um reguläre Sprachen, also solche Sprachen die mit regulären Ausdrücken oder endlichen Automaten beschreiben lassen.
Nun lese ich hier im Buch, dass die folgende Sprache regulär ist...
L = {w element {0,1}* | |w|1 <= 2}
Es handelt sich also um die Sprache, die alle Wörter enthält, deren Wörter höchstens zwei Einsen enthalten.
Ich kann dafür ja ohne Probleme einen endlichen Automaten oder regulären Ausdruck konstruieren, der das nachweist und hätte somit gezeigt, dass sie regulär ist.
Allerdings müsste dafür ja auch das Pumping Lemma gelten, dass bekanntlich besagt, dass es für eine reguläre Sprache ein n>=1 gibt, sodass für alle Wörter der Länge >= n eine Zerlegung in w=xyz existiert ( |xy| <= n, y nicht leer). Ferner muss dann für jedes i>=0 das Wort xy^iz wieder in der Sprache liegen, was beim Verfielfältigen von Einsen ja nicht sein würde.
... ach verdammt, jetzt ist mir mein Denkfehler gerade beim Schreiben aufgefallen. *g* Es muss ja nur eine Zerlegung gelten und sobald das Wort mindestens die Länge 3 hat, kann ich das y als die 0 auffassen, was sich ja beliebig aufpumpen lässt.
Ich lass den Thread trotzdem mal hier, falls ich noch mal Fragen habe oder es noch einmal nachlesen will.