Regularität bei formalen Sprachen
Beweis: Endliche Sprachen sind regulär
Wir definieren einfach eine beliebige endliche Sprache:
Alphabet:
∑= {0,1}
Endliche Sprache:
L= {001, 110, 101}
Anschließend modellieren wir die Sprache als Binärbaum, wobei auch Fehlzustände miteinbezogen werden:
Alle blau durchkreuzten Knotenpunkte sind Fehlzustände.
Die restlichen Knoten der dritten Zeile sind Endzustände.
Der Binärbaum wird nicht weitergeführt, weil keine der Wörter der endlichen Sprache eine Wortlänge größer 3 aufweist.
Definiert man die Knoten als Zustände, erhält man einen endlichen Automaten, welcher die endliche regulären Sprache modelliert.
Nicht reguläre Sprachen:
Erklärung + Beispiel
L= {w
Obiges Beispiel zeigt eine Sprache, die nicht regulär ist.
Dies gilt allerdings nur dann, wenn n keinen festen Wert hat.
Hat n ein fester Wert, so ist die Sprache endlich.
Da alle endlichen Sprachen regulär sind, wäre die Sprache bei einem festen Wert n folglich regulär.
Der obige Binärbaum zeigt alle Übergangsfunktionen, die bei 4 Eingaben der Elemente a und b gebildet werden können (exklusive leerem Wort).
Der Automat weiß nur anhand des Zustandes Z2, dass bereits 2mal a eingeben wurde und kein drittes Mal mehr eingeben werden darf, um der Definition der Sprache L={aabb} zu entsprechen.
Bei einem beliebigen n müsste folgender Binärbaum in Abhängigkeit zur Ausprägung von N jeweils angepasst werden.
Dies wiederspricht allerdings der grundlegenden Eigenschaft eines endlichen Automaten, dass die Menge der Zustände und Endzustände sowie den damit einhergehenden Übergangsfunktionen vor Eingabe bereits fest definiert sein muss.
Gleiche Erklärung- Andere Worte
L= {w
Wir nehmen an, dass n nicht fest definiert ist und somit alle Werte annehmen kann.
Um alle Wörter zu akzeptieren, muss der Automat zählen können,
wie oft a und
wie oft b
vorgekommen ist.
Wieso?
Es gilt -> a und b müssen also beide n-mal hintereinander auftreten, damit sie vom Automaten akzeptiert werden, wobei gilt, dass n jeweils äquivalent bzw. gleich hoch ist.
Ist n begrenzt, so kann der Automat über die Zustände prüfen, ob akzeptiert wird
Das Wichtigste:
Dieser Abschnitt hat gezeigt, dass endliche Sprachen immer regulär sind, da die Zustandsübergänge durch die Endlichkeit entsprechend angepasst werden können.
Beispielbezogene Propositionen
Ist n nicht fest definiert, d.h., n kann alle Werte annehmen, dann müsste der Automat eine der drei folgenden Bedingungen erfüllen…
1. sich entsprechend dem n hinsichtlich der Zustände ändern.
Da die Zustände sich jedoch nicht ändern können, sondern integraler Bestandteil eines DFAs sind, kann die Sprache nicht regulär sein.
2. unendlich viele Zustände haben, um n zu akzeptieren
Die Begrenzung auf eine Anzahl von Zuständen ist aus hardware- bzw. physischer Sicht unmöglich.
3. pumpbare Elemente haben, um n zu akzeptieren, wobei die Anzahl der Iterationen (Schleifen, wiederholungen eines pumpbaren Wortbestandteils) gezählt werden müssen
Die dritte Bedingung ist umsetzbar, wenn die Anzahl der Iterationen nicht gezählt werden muss, weil die Sprache keine Bedingungen für die Anzahl von den iterierten Wortbestandteilen setzt.
Bei unserem Beispiel L= {w
Ist jedoch durch die Äquivalenz von n eine Bedingung geknüpft bezüglich der Häufigkeit von a und b:
Sie müssen gleich oft vorkommen.
Somit ist die Sprache nicht regulär (vgl. nächster Abschnitt)
Unendliche Sprachen und ihre Regularität
Auch unendliche Sprachen können jedoch ebenfalls regulär sein.
Ein Automat kann Symbole beliebig oft wiederholen und somit theoretisch unendlich lange Wörter ausgeben, wenn er endlich viele Zustände hat.
Dies ist dann der Fall, wenn die Anzahl der Wiederholung eines Symbols für die Terminierung unerheblich ist (vgl. 3.Proposition letzte Seite)
Dies ist dann der Fall, wenn man eine Schleife einbaut, welche beliebig oft und damit inbegriffen auch gar nicht durchlaufen werden kann, ohne dass sich was an der Akzeptanz des Wortes und an Zustandsanzahl des DFA ändert.
Die Art von Schleifen bezeichnet man auch als pumbare Teile. Sie kommen im Kontext des Beweises des Attributes „Regulär“ als mathematisches Beweisverfahren auch unter dem Namen Pumping Lemma zum Einsatz.
Pumping Lemma:
Wie bereits im obigen Abschnitt beschrieben, dient das Pumping Lemma als Beweisverfahrung zur Prüfung, ob eine Sprache regulär ist oder nicht.
Eine Sprache ist regulär, wenn sie eine abzählbare endliche Menge über dem Alphabet inklusive dem leere Wort ε darstellt ().
Die zweite Bedingung für eine reguläre Sprache ist ihre Akzeptanz durch einen gegebenen Automaten, welcher die Eingabesymbole aus dem Alphabet entgegennimmt.
Ein DFA kann die Anzahl der eingebenden Symbole nicht speichern.
L(DFA)=
Die einzige Möglichkeit mit einem DFA zu definieren, dass z.B nach 000 die Symbole 111 folgen sollen, stellen die Zustände dar.
Ist die Anzahl der Nullen (000=N(o)=3) und Einsen (111=N (1)=3) im Vorhinein festgelegt, lässt sich ein DFA erstellen, welcher die Sprache (000111) akzeptieren kann, indem drei Zustandsübergänge durch Eingabe von 0 und drei Zustandsübergänge durch Eingabe von 1 definiert werden, sodass das Wort 000111 mittels 6 Zustandsübergängen und ihren zugehörigen Übergangsfunktionen das Wort 000111 in einen Endzustand überführen und somit dafür sorgen, dass das Wort akzeptiert wird.
Ist N (0)=3 und N (1)=3 nicht festgelegt, sodass N eine Variable darstellt, lässt sich die Sprache folgendermaßen definieren:
L(DFA)=
Mögliche Wörter der Sprache wären also:
01
0011
000111
00001111
….
0 n1 n
Da der Automat in Abhängigkeit zu n seine Zustände und Übergangsfunktionen ändern müsste, kann die Sprache nicht regulär sein.
Kontraposition als Beweisverfahren
Ob eine Sprache regulär ist oder nicht lässt sich formal beweisen, indem man die Kontraposition des Pumping-Lemma nutzt.
Grundsatz hierfür ist das Verständnis die Pumping-Lemmas.
Das Pumping-Lemma ergibt sich aus der Tatsache, dass es Sprachen gibt, die Zeichen enthalten, dessen Anzahl ebenfalls variable ist.
Das klassische Beispiel hierfür stellt folgende Sprache dar.
In diesem Fall kann y beliebig oft wiederholt werden, ohne dass sich deren Anzahl durch die Anzahl der Zustände gespeichert werden muss. Dies lässt sich auf die Eigenschaften eines Kreises/einer Schleife/einen pumpbaren Wortbestand zurückführen. Man sagt auch, y lässt sich beliebig oft pumpen.
Klassischer Anwendungsfall für einen solchen pumpbaren Bestandteil ist eine Schleife.
Enthält ein Automat keine Kreise oder Schleifen, so ist die Anzahl der Zustandsübergänge identisch mit der Anzahl der Zustandsübergangsfunktionen und identisch mit der Wortlänge
Alle von dem obig abgebildeten Automaten Wörter sind begrenzt auf die Länge |x|=2, welches der Anzahl der Zustandsübergänge und entspricht.
Ein Automat ohne Kreise bzw. Schleifen ist also hinsichtlich der Wortlänge begrenzt durch die Anzahl der Zustandsübergänge (Übergangsfunktionen):
è N=2=Zustandsübergänge=|x|
Durch die Implementierung von Schleifen bzw. Kreisen kann die Wortlänge |x| beliebig verlängert, ohne dass die Anzahl der Zustandsübergänge erhöht werden muss (N=2).
Führen wir nach dem ersten Zustandsübergang eine Schleife ein, so kann die Wortlänge |x| beliebig verlängert werden, sodass die Wortlänge N=2 bzw. N=3 (wenn Schleife als Zustandsübergang gezählt wird) kleiner wird als die Wortlänge |x|.