Hallo zusammen, es geht weiter mit der Vorlesung.
Wir beschäftigen uns ja in der Vorlesung im Moment mit regulären
Sprachen und mit endlichen Automaten.
Und nochmal ganz kurz zur Erinnerung, was in der letzten Vorlesung
insbesondere besprochen wurde.
Also Sie kennen endliche Automaten, Sie kennen reguläre Sprachen, also
sozusagen die Definition.
Und da ist eben die Frage aufgetaucht, haben die beiden Konzepte
irgendwas miteinander zu tun?
Und als allererstes sozusagen die Idee zu beweisen, dass es für jede
reguläre Sprache einen endlichen Automaten gibt, der diese akzeptiert.
Dann haben sie mal angefangen, das zu beweisen.
Zu dem Zeitpunkt kannten sie nur deterministische endliche Automaten
und da hat sich sehr schnell gezeigt, dass man sozusagen den
Determinismus aufgeben würde, dass es vielleicht leichter geht, das zu
zeigen.
Sozusagen eine reguläre Sprache hernehmt und entsprechend der Art und
Weise, wie diese reguläre Sprache aufgebaut ist, dann einen endlichen
Automaten konstruiert, der diese akzeptiert.
Dann wurde der Beweis sozusagen unterbrochen oder zurückgestellt und
jetzt mal das Konzept nicht deterministischer endlicher Automaten
angeschaut.
Zur Erinnerung, bei deterministischen endlichen Automaten ist die
Übergangsfunktion eine Funktion, die also ganz eindeutig für jeden
Zustand und jedes mögliche Symbol aus dem Alphabet, das man in dem
Zustand lesen kann, sagt, was der Folgezustand ist.
Dem gegenübergestellt wurde das Konzept des nicht deterministischen
endlichen Automaten, nicht Determinismus, das heißt, es gibt eventuell
Wahlmöglichkeiten, wenn man in einem Zustand ist, ein bestimmtes
Symbol liest, das heißt, es gibt nicht den einen eindeutigen
Folgezustand, sondern aus dem Zustand kann man bei Lesen eines Symbols
in verschiedene Zustände übergehen und es kann sogar so sein, dass man
ohne Lesen eines Symbols in einen anderen Zustand übergehen kann, also
dass es Epsilon-Übergänge gibt.
Da würde sich natürlich gleich mal die Frage stellen, was heißt denn
dann noch Akzeptieren, wenn man ein nicht deterministisches
Berechnungsmodell hat.
Beim deterministischen Berechnungsmodell ist das ganz klar, Sie haben
Ihren Automaten, es gibt die ausgezeichneten Endzustände und alle
Wörter, die vom Anfangszustand in einen Endzustand führen, werden
akzeptiert.
Und da das eindeutig ist, was passiert, wenn Sie ein Wort lesen, ist
das eine ganz klare Sache, was Akzeptieren heißt.
Bei einem nicht deterministischen Modell könnte es jetzt so sein, dass
Sie, wenn Sie ein bestimmtes Wort eingeben, der Automat nach
Abarbeitung des Wortes mal in dem einen, mal in dem anderen Zustand
endet.
Und da fragt man sich schon, wie definiere ich denn dann Akzeptieren?
Akzeptieren ist so definiert, dass ein Wort genau dann akzeptiert
wird, wenn es eine Abarbeitung nicht deterministischen endlichen
Automaten gibt, bei Lesen dieses Wortes in einem Endzustand endet.
Eine gibt, aber es kann viele verschiedene geben, einige enden in
Endzuständen.
So, jetzt haben wir also diese beiden Modelle erstmal und da stellt
sich natürlich die Frage, sind die äquivalent?
Sie haben bewiesen, die sind äquivalent.
Das heißt, wenn Sie einen beliebigen nicht deterministischen Automaten
hernehmen, können Sie dazu einen deterministischen endlichen Automaten
konstruieren, der genau dieselbe Sprache akzeptiert.
Die Konstruktion war die sogenannte Potenzmengenkonstruktion.
Potenzmengenkonstruktion deshalb, weil Sie beim Übergang von der
Zustandsmenge Ihres nicht deterministischen endlichen Automaten zu
einem äquivalenten deterministischen endlichen Automaten als
potenzielle Zustandsmenge des deterministischen endlichen Automaten
die Potenzmenge der Zustandsmenge nicht deterministischen endlichen
Automaten hernehmen.
Und das ist irgendwie klar, dass dabei die Größe von Ihrem Konstrukt
explodiert.
Zumindest kann das vorkommen.
Von N Zuständen beim nicht deterministischen endlichen Automaten
können Sie potenziell zu 2 hoch N Zuständen des äquivalenten
deterministischen Automaten kommen.
Das behalten wir im Hinterkopf, da müssen wir uns nochmal mit
beschäftigen.
Aber nachdem Sie also dies bewiesen haben, zu jedem nicht
deterministischen endlichen Automaten gibt es einen äquivalenten
deterministischen endlichen Automaten, sind Sie dann zurückgegangen zu
dem, was Sie eigentlich zeigen wollten, nämlich dass es für jede
reguläre Sprache einen endlichen Automaten gibt, der diese akzeptiert.
Dann war es plötzlich einfach, man schaut sich einfach an, wie sind
reguläre Sprachen aufgebaut und entsprechend dem Aufbau gibt man
endliche Automaten an, die genau die entsprechenden Sprachen
akzeptieren.
Und diese endlichen Automaten, die da konstruiert wurden, die waren
nicht deterministisch, aber das macht nichts.
Die nicht deterministischen können Sie dann jeweils auch per
Potenzmengenkonstruktion einen deterministischen endlichen Automaten
bauen.
Und nur zur Erinnerung, so sahen die drei Hauptkonstruktionen aus.
Also nochmal, jede reguläre Sprache wird von einem deterministischen
endlichen Automaten akzeptiert.
Wir schauen uns an, wie sind reguläre Sprachen aufgebaut.
Sie sind so aufgebaut, man startet mit Anfangssprachen.
Die reguläre Sprache ist regulär und die einelementigen Sprachen sind
regulär und aus regulären Sprachen können Sie neue reguläre Sprachen
bauen, per Vereinigung, per Produktbildung und per klinischer
Abschluss.
Endliche Automaten anzugeben für die leere Menge oder einelementige
Sprachen ist trivial.
Das steht jetzt hier nicht mehr auf der Folie.
Und dann müssen Sie einfach induktiv sagen, naja gut, wenn ich
endliche Automaten habe zu zwei regulären Sprachen, dann kann ich aus
den beiden auch einbauen für die Vereinigung dieser beiden Sprachen.
Für das Produkt dieser beiden Sprachen oder für eine reguläre Sprache
kann ich aus dem Automaten für diese reguläre Sprache einbauen für den
klinischen Abschluss.
Und diese Automaten, die man da baut, die sahen also so aus.
Vereinigung, da muss man ja einfach die beiden Automaten nebeneinander
stellen und von einem neuen Startzustand, den man neu dazu nimmt,
einfach Epsilon-Übergänge in die Anfangs- oder Startzustände des einen
und des anderen zulassen.
Der Rest bleibt gleich, also die Endzustände, Vereinigung der
Endzustandsmengen der beiden Automaten.
Und für das Produkt müssen Sie einfach so etwas hintereinander
schalten und für den klinischen Abschluss einfach so einen Zykel
einbauen.
Aber Sie sehen hier, die sind hochgradig, in Anführungszeichen nicht
deterministisch.
Sie brauchen hier insbesondere Epsilon-Übergänge.
Okay, was bleibt jetzt noch zu tun oder was könnte man sich jetzt noch
so alles fragen?
Man könnte sich angesichts dieses Satzes insbesondere auch fragen,
gilt auch die Umkehrung?
Gibt es zu jedem endlichen Automaten eine reguläre Sprache?
Die Frage ist, sind die regulären Sprachen genau die Automaten?
Der Frage werden wir uns gleich widmen, ich werde aber noch eine Sache
zwischenschalten, die irgendwie zu dieser Potenzmengen-Konstruktion
gut passt.
Wenn Sie sich so nicht-deterministische endliche Automaten angucken,
dann drückt sich der Nicht-Determinismus in zwei Dingen aus.
In den Epsilon-Übergängen und in den Wahlmöglichkeiten.
Und wie ich eben gesagt habe, Sie erinnern sich, diesen Nicht
-Determinismus sozusagen wegzukonstruieren, der Potenzmengen
-Konstruktion führt zu einer Explosion der Zustandsmenge.
Also Sie kriegen sozusagen exponentiell viele Zustände bei dieser
Potenzmenge.
Und die Frage ist jetzt, kann ich denn allein die Epsilon-Übergänge
unterdrücken, ohne dass meine Zustandsmenge stark anwächst?
Und dieser Satz hier sagt, ja, das geht.
Der Satz sagt, zu jedem Nicht-Deterministischen Endlichen Automaten A
mit Epsilon-Übergängen gibt es einen Nicht-Deterministischen Endlichen
Automaten, nennen wir den A-Schlange, ohne Epsilon-Übergänge, der
äquivalent ist, also dieselbe Sprache akzeptiert und nicht mehr
Zustände hat.
Also um die Epsilon-Übergänge loszuwerden, brauche ich jetzt keine
Erweiterung der Zustände.
Aber das überlegen wir uns mal ganz schnell, das ist wirklich nichts
Schwieriges.
Es ist wie gesagt auch nur gut zu wissen.
Schauen wir uns mal hier dieses Beispiel an.
Also ein ganz einfacher, kleiner Nicht-Deterministischer Endlicher
Automat mit Epsilon-Übergängen.
Also es gibt einen Epsilon-Übergang von S nach T, es gibt einen
Epsilon -Übergang vom Zustand U zum Zustand F.
Wie kann ich diese Epsilon-Übergänge loswerden?
Ich fange mal von hinten an.
Also hier habe ich mir so eine Tabelle gemacht mit den Zuständen.
Und wenn ich von hinten anfange, naja gut, ich muss so den Epsilon
-Abschluss von den Zuständen bilden und dann die Übergangsfunktion
anpassen auf sozusagen die neuen Zustände.
Wenn ich den Epsilon-Abschluss von F, von unserem Endzustand hier
bilde, dann ist das nichts anderes als F, denn von F nach F oder von F
gibt es keinen Epsilon-Übergang zu irgendeinem anderen Zustand.
Diesen von Epsilon bleibe ich hier in F.
Und dementsprechend ändert sich hier auch nichts an der
Übergangsfunktion.
Der Automat ist sehr klein, bewusst, damit wir hier bei der
Konstruktion nicht zu viel angucken müssen.
Insbesondere haben wir hier nur ein Symbol.
Das Alphabet enthält nur A.
Das heißt, ich muss, wenn ich die neue Übergangsfunktion bilde, auch
nur dieses eine Symbol angucken.
Also wenn ich jetzt von F aus schauen will, wenn ich jetzt den Epsilon
-Abschluss von F betrachte und betrachte, wo komme ich denn dahin bei
Lesen von A, muss ich also nur schauen, da der Epsilon-Abschluss von
F, F ist, wo komme ich denn durch Lesen von A hin und muss keine
anderen Symbole angucken.
Und das ist wieder F.
Hier hinten ist klar, was passiert.
So, und jetzt arbeite ich mich nach vorne.
Ich gucke mir das U an.
Ich gucke mir an, wo komme ich denn durch Lesen von Epsilon von U aus
hin.
Was ist der Epsilon-Abschluss von U?
Entweder komme ich durch Lesen von Epsilon von U nach U, also bleibe
bei U oder weil es einen echten Epsilon-Übergang zu F gibt, komme ich
zu F.
Das heißt, der Epsilon-Abschluss von U ist U, F.
Und jetzt muss ich mir nur angucken, wo komme ich hin, wenn ich von U
aus A lese.
Kann ich erstmal Epsilon lesen und dann A lesen?
Oder angucken, was passiert, wenn ich von U aus direkt A lese.
Wir haben uns ja gesagt, dass wir bei nicht-deterministischen
endlichen Automaten nur die echten Übergänge, die es gibt, hinmalen.
Und hier gibt es nur einen Übergang bei Lesen von Epsilon.
Wenn ich aus Epsilon sozusagen loswerden will, muss ich also jetzt den
Epsilon -Abschluss von U angucken und gucken, wo führt mich die
Übergangsfunktion denn hin vom Epsilon-Abschluss von U aus, wenn ich A
lese.
Und das ist hier F.
Und dann arbeite ich mich weiter vor.
Ich gucke mir T an.
Der Epsilon-Abschluss von T ist T.
Von T aus gibt es keinen weiteren Epsilon-Übergang.
Lesen von A führt mich von T aus nach U.
Aber von U aus komme ich auch mit Epsilon nach F.
Das heißt, vom Epsilon-Abschluss von T aus komme ich bei Lesen von A
nach U und nach F.
Sozusagen bei der Sache hier habe ich als echten Übergang für meinen
Automaten, bei denen die Epsilon-Übergänge unterdrückt wurden, von U
bei Lesen von A diesen hier entdeckt.
Deshalb ist er hier jetzt grün eingezeichnet.
Und hier habe ich jetzt entdeckt, na gut, das gab es vorher schon, und
das hier gibt es noch als direkten Übergang bei Lesen von A von T aus,
wenn ich hier sozusagen diesen Epsilon-Übergang einbeziehe, um ihn
dann nicht mehr zu verwenden.
Hier habe ich den echten Übergang von T nach F bei Lesen von A
entdeckt.
So, und jetzt gehe ich eben wieder eins vor, gucke mir S an, den
Epsilon -Abschluss von S, das ist ST, von S aus kann ich durch Lesen
von Epsilon bei S bleiben oder zu T kommen, und dann der entsprechende
Übergang bei Lesen von A.
Ich komme nach U, und von U aus komme ich auch nach F.
Das heißt also, Delta Epsilon-Abschluss von S, A SUF.
Und das heißt insgesamt, ich habe diese grünen Übergänge sozusagen
ermittelt, durch sozusagen unterdrückende Epsilon-Übergänge.
Was ich also bekomme jetzt ist folgender nicht deterministischer
endlicher Automat, der dasselbe kann wie der, den ich vorher auf der
Folie hatte, der aber keine Epsilon-Übergänge mehr hat.
Der hat die gleiche Anzahl von Zuständen.
Weil ich mache hier so eine Art Potenzmengen-Konstruktion, nur für
jeden Zustand kommt dann nur eine Menge von Zuständen rein, der
Epsilon -Übergang des Zustands, sonst nichts.
Und die kann ich dann wieder gleichsetzen.
Und das machen wir jetzt einfach formal in diesem Beweis.
Also ich habe so einen endlichen Automaten A, der ist nicht
deterministisch, der hat Epsilon-Übergänge, und dazu baue ich jetzt
eine Schlange, einen neuen, nicht deterministischen endlichen
Automaten, der keine Epsilon-Übergänge hat, und das mache ich wie
folgt.
Erstmal bei der Zustandsmenge, da kann ich im Wesentlichen dieselbe
Menge nehmen.
Ich muss allerdings bei den Endzuständen aufpassen.
Sie können über Epsilon-Übergänge von einem Nicht-Endzustand in einen
Endzustand kommen, in ihrem nicht deterministischen endlichen
Automaten mit Epsilon-Übergängen.
Und wenn ich die Epsilon-Übergänge sozusagen unterdrücke, durch die
Konstruktion, die wir eben im Beispiel hatten, heißt das also, dass
sie Zustände, die vorher Nicht-Endzustände waren, als Endzustände
interpretieren müssen.
Weil die entsprechende Menge, die dazu gehört, der Epsilon-Abschluss,
einen Endzustand enthält.
Und deshalb definieren wir Q-Schlange so, dass wir aus Q F rausnehmen
und eine neue Endzustandsmenge F-Schlange definieren.
Und das soll gerade die Menge der Zustände sein, deren Epsilon
-Abschluss einen nicht leeren Schlitt mit der Zustandsmenge hat, für
den Ausgangsautomaten.
Hier ein Beispiel.
Haben wir das noch nicht eingezeichnet.
Da hier der Epsilon-Abschluss von U F enthält, ist das hier auch ein
Endzustand.
Der Startzustand bleibt der gleiche und die Übergangsfunktion ist
jetzt klar.
Im Prinzip nehme ich, wenn ich die Schlange von Q,A bilde, den Epsilon
-Abschluss von Q und schaue, wo komme ich denn durch Lesen von A von
da aus hin.
Und ich muss natürlich für den Fall, dass A gleich Epsilon ist, noch
den Übergang definieren.
Nun in unserem endlichen Automat, ohne Epsilon-Übergänge, bleibt man
im Zustand D.
Das heißt also, Delta-Schlange von Q,A ist einfach Q, wenn A Epsilon
ist und ist ansonsten Delta, die Übergangsfunktion unseres
Ausgangsautomaten, von Epsilon-Abschluss von Q,A.
That's it.
Und auf die Art bekommen Sie nicht mehr Zustände und die Sprache, die
akzeptiert wird, ist auch dieselbe, per Konstruktion.
Also das ist keine schwierige Sache, aber es ist gut zu wissen, dass
das Loswerden von Epsilon-Übergängen bei einem nicht deterministischen
endlichen Automat noch nicht zu einem Anwachsen der Zustandsslänge
führt.
Das kommt erst rein, wenn Sie die Wahlmöglichkeiten loswerden wollen.
Jetzt aber zu der wichtigeren Frage, die wir eben gestellt haben.
Wie ist das denn, wenn ich jetzt einfach einen endlichen Automaten
habe?
Was ist denn die Eigenschaft der entsprechenden Sprache?
Also wir haben schon festgestellt, für den regulären Sprachen gehören
die endlichen Automaten in dem Sinne, dass ich zu jeder regulären
Sprache einen endlichen Automaten angeben kann, der diese akzeptiert.
Und das ist jetzt sozusagen die Umkehrung.
Kann ich auch für jeden endlichen Automaten eine entsprechende
reguläre Sprache angeben, die genau die ist, die von dem endlichen
Automaten akzeptiert wird?
Also insgesamt heißt das dann, wenn der Satz auch stimmt, die
regulären Sprachen, das sind genau die Sprachen, die von endlichen
Automaten akzeptiert werden.
Also wir wollen beweisen, jede Sprache, die von einem endlichen
Automaten erkannt wird, ist regulär.
Und wenn das keine Rolle spielt, ob wir es jetzt mit einem
deterministischen oder nicht deterministischen endlichen Automaten zu
tun haben, sagen wir das auch nicht dazu.
Da wir jetzt wissen, deterministische und nicht deterministische
endliche Automaten sind äquivalent, können dasselbe, ist das bei dem
Satz jetzt auch nicht relevant, sozusagen, dass jede Sprache, die von
einem deterministischen oder nicht deterministischen endlichen
Automaten erkannt wird, dass jede solche Sprache regulär ist.
Ja, das müssen wir beweisen.
Wie beweist man sowas?
Naja, jetzt starten wir von dem endlichen Automaten und wir müssen
jetzt sozusagen die Sprache, die von dem endlichen Automaten
akzeptiert wird, so beschreiben, dass man der Beschreibung ansieht,
dass diese Sprache regulär ist.
Das heißt, die Beschreibung sollte möglichst Beschreibung durch einen
regulären Ausdruck sein.
Das wäre natürlich auch schön, wenn wir das systematisch machen
könnten, sodass wir, wenn wir jetzt mal in Zukunft irgendeinen
endlichen Automaten vorgelegt bekommen, nicht nur durch, ich sag mal,
scharfes Hinsehen versuchen können, zu sagen, welche Sprache das ist,
die von dem Automaten akzeptiert wird, sondern wirklich, dass wir
durch eine Konstruktion diese Sprache auch aufbauen können.
So, es ist hier ganz praktisch, bei einem deterministischen endlichen
Automaten zu starten.
Diese Konstruktion wird so sein, dass Sie aus dem deterministischen
endlichen Automaten einen regulären Ausdruck bauen können, der die
Sprache beschreibt, die von diesem deterministischen endlichen
Automaten akzeptiert wird.
Wenn Sie einen nicht deterministischen endlichen Automaten vorgelegt
bekommen, müssen Sie möglicherweise erst mal diesen Umweg gehen, per
Potenzmengenkonstruktion einen deterministischen endlichen Automaten
ausbauen und dann die Konstruktion, die hier im Beweis kommt,
anwenden, um zur regulären Sprache zu kommen.
Also was wir machen müssen ist, wir müssen zeigen, dass die Sprache,
die von dem DAA akzeptiert wird, regulär ist.
Was ist die Sprache, die von dem DAA akzeptiert wird?
Das ist die Menge all der Worte aus Sigma-Stern, deren Abarbeitung von
S in einen Endzustand führt.
Also L gleich Menge aller W aus Sigma-Stern, A endet nach Abarbeitung
von W in einem Zustand aus der Menge F.
So können wir diese Sprache L von A beschreiben.
Der Beschreibung sieht man jetzt noch nicht an, dass das eine reguläre
Sprache ist.
Wir müssen jetzt die Arbeitsweise des endlichen Automaten irgendwie
benutzen.
Dafür gucken wir uns mal an, wie so eine Abarbeitung eines Wortes
aussieht.
Bei einem Wort W gleich A1 bis AK, also irgendein Wort der Länge K aus
Sigma -Stern, passiert folgendes.
Das erste Symbol führt uns vom Startzustand aus in einen anderen
Zustand.
Anders, der muss nicht verschieden sein.
Das nächste Symbol wieder in einen Zustand, das nächste Symbol wieder
in einen Zustand und so weiter.
Also A1 bis AK führt uns irgendwie von dem ersten Zustand S zu einem
weiteren Zustand, zum weiteren Zustand, zum weiteren Zustand und so
weiter.
Also Abarbeitung von A1 bis AK bewirkt das Durchlaufen von Zuständen
S, Q1, Q2, Q3 und so weiter bis QK.
Und diese Zustände, die müssen nicht verschieden sein.
Bei der Abarbeitung kann das schon irgendwie mal so im Kreis gehen.
Und wir suchen jetzt, wir interessieren uns für die Wörter, die
akzeptiert werden von dem endlichen Automaten, wo uns A1 bis AK also
in einen QK führt, das Endzustand ist.
Wir suchen die Wörter, sodass der letzte Zustand in F ist.
So und jetzt ist der erste Schritt, wir reduzieren jetzt so ein
bisschen die Sprache, die wir beschreiben wollen, auf Teilsprachen.
Dass wir über Teilsprachen angelangt sind, die wir so beschreiben
können, dass man sieht, die sind regulär.
Und unsere Reduzierung ist so, dass man von denen dann aber auch zur
Ausgangssprache kommt, durch nur sowas wie Vereinigung oder
Produktbildung oder klinische Abschlussbildung.
Und das allererste, was wir machen können, ist, dass wir einfach
getrennt für jeden Endzustand nachschauen, wie sieht denn die Sprache
aus, die aus den Worten besteht, deren Abarbeitung uns in diesen
bestimmten Endzustand führt.
Wenn wir für jede dieser Sprachen, also wir gehen alle Endzustände aus
F durch, wenn wir für jede dieser Sprachen eine reguläre Beschreibung,
einen regulären Ausdruck angeben können, dann ist auch die Vereinigung
dieser Sprachen regulär.
Das heißt also, dann ist die Sprache, die uns interessiert, auch
regulär.
Also wir brauchen eigentlich nur, ich sag mal, LF anzugucken.
Hier steht es auch.
Zu F Endzustand definiere LF als die Menge der Wörter aus Sigma Stern.
A endet nach Abarbeitung dieses Wortes in F.
Und die kann ich auch anders hinschreiben.
Die Menge der Wörter aus B aus Sigma Stern.
B überführt S in F im Automaten A.
Das ist jetzt irgendwie so ganz wichtig.
Wir schauen uns also jetzt wieder an, was passiert bei der
Abarbeitung.
Was werden da an Zwischenzustände durchlaufen?
Wir versuchen danach, das Ganze nochmal aufzuspalten.
Also wenn wir all diese LF für alle kleinen F aus Groß F haben, dann
ist ja die Sprache, die uns interessiert, gerade die Vereinigung über
kleinen F aus Groß S, F LF.
Und wenn diese kleinen F regulär sind, dann ist auch diese Vereinigung
regulär.
So, das L klein F.
Menge der Wörter aus Sigma Stern.
W überführt S in klein F in dem Automaten A.
So, jetzt geht es ans wirkliche Konstruieren.
Jetzt nummerieren wir unsere Zustände einfach durch, irgendwie.
Q1 bis QN.
Unser Automat habe N Zustände.
Das nennen wir die Q1 bis QN.
Und dann definieren wir für jedes Zustandspaar QRQT die Sprache LQRQT
als die Sprache der Wörter Sigma Stern, die von QR nach QT führen.
Das sind jetzt allgemeinere Sprachen als die Sprache zu dem Automat.
Einfach nur die Wörter, die von einem Zustand, den wir QR nennen, zu
einem Zustand, den wir QT nennen, führen.
Das ist für alle Zustandspaare.
Egal, ob es N Zustände oder nicht N Zustände sind.
Schauen wir uns mal die an.
Wenn wir die alle als reguläre Sprachen durch reguläre Ausdrücke
beschreiben können, dann wissen wir insbesondere auch, dass die
Sprache LF, die uns hier interessiert, regulär ist.
Nämlich, die ist eine von der Sorte.
Die ist nämlich so geschrieben, L unten kleinen s, kleinen f.
Also QR ist s, QT ist kleinen f.
Und diese LQRQT für beliebige Zustandspaare QRQT, die unterteilen wir
jetzt noch weiter.
LQRQT, das sind einfach die Wörter, die von QR nach QT führen, in A.
Über irgendwelche Zwischenzustände.
Jetzt machen wir dieses irgendwelche Zwischenzustände ein bisschen
spezifischer und sagen, wir gucken systematisch an, welche Zustände
wir als Zwischenzustände erlauben.
Und dafür ist diese Nummerierung wichtig.
Wir haben die irgendwie nach irgendeiner Reihenfolge durchnummeriert,
die Zustände in Q1 bis QN.
Und jetzt schauen wir sozusagen als potenzielle Zwischenzustände an.
Nur Q1.
Oder Q1, Q2.
Oder Q1, Q2, Q3.
Oder Q1 bis QI.
Für alle Möglichkeiten, was I sein kann, also auch bis zu QN hin.
Also wir definieren jetzt nochmal als eine Teilsprache von LQRQT,
LQRIQT.
Und das soll die Menge der W aus Sigma Stern sein, für die gilt,
Abarbeitung von W, ausgehend von QR, führt nach QT.
Aber dazwischen werden nur Zustände aus Q1 bis QI durchlaufen.
Also wir gucken sozusagen von unserer Zustandsmenge Q1 bis QN immer
diese Anfangsstücke an.
Für alle I.
Und sagen, nur die sollen erlaubt sein als Zwischenzustände.
Also hier haben wir jetzt eine ganze Menge von Sprachen.
Alle möglichen Paare QRQT kommen hier in Frage.
Und als Zwischenzustände für jedes I jeweils die Menge Q1 bis QI.
Also anders ausgedrückt oder mal hingemalt.
Also W ist in QRIQT, wenn W also folgendes bewirkt.
Bei Abarbeiten von W kommen wir von QR nach QT und dazwischen
durchlaufen werden nur Zustände aus Q1 bis QI.
Wenn wir diese Sprachen alle durch reguläre Ausdrücke beschreiben
können, dann können wir auch folgende Sprache durch einen regulären
Ausdruck beschreiben.
Die Sprache, die wir hier LQRQT genannt haben, die ist nämlich in der
Schreibweise nichts anderes als LQR, N, QT.
Also das N steht für alle Zustände, Q1 bis QN sind als
Zwischenzustände.
Wenn die alle regulär sind, dann ist auch die regulär.
Wenn die regulär ist, dann ist auch unser LSF regulär.
Und dann ist auch unsere Vereinigung über alle Endzustände LF.
Und an die hier kommen wir jetzt von unten ran.
Indem wir erstmal gar keinen Zwischenzustand erlauben, dann nur Q1 als
Zwischenzustand erlauben, dann nur Q1, Q2 und so weiter.
Und das Prinzip, das hier angewendet wird, ein algorithmisches
Prinzip, das Sie kennen, ist ein Prinzip der dynamischen
Programmierung.
Wir fangen so bei 0 an, dann 1 und so weiter.
Und dann irgendwann mal allgemein, wie können wir LQR, I plus 1, QT
ausdrücken, indem wir LQR, I plus 1, QT zurückführen auf irgendwelche
LQR, I, QT.
Also, wir zeigen LQR, I, QT ist für beliebige zustandsbare QR, QT aus
Q und beliebiges I zwischen 1 und N regulär.
Und das machen wir systematisch von unten.
Wir betrachten zunächst direkte Übergänge, also I gleich 0.
Also kein Zwischenzustand ist erlaubt.
Also per sozusagen Definition ist LQR 0 QT die Menge der Worte, die
von QR nach QT führt, ohne überhaupt einen Zwischenzustand zu
benutzen.
Abarbeitung von W führt von QR nach QT ohne Zwischenzustand.
Jetzt gibt es zwei Fälle, entweder das R ist gleich T oder das R ist
ungleich T.
Wenn R gleich T ist, dann ist also QR gleich QT.
Dann ist LQR 0 QT die Menge der Symbole, für die gilt Delta QTA ist
wieder QT.
Das QR ist ja gleich QT.
Also alle Symbole, die vom Zustand zu sich selbst führen.
Und, und deshalb ist das jetzt wichtig, dass wir hier genau hingucken,
natürlich Epsilon.
Epsilon kommt hier jetzt rein.
Denn bei dem Zustand bleiben, das ist ja nichts anderes als das, was
wir hier betrachten, tun wir auch, indem wir Epsilon lesen.
Also für R gleich T oder QR gleich QT ist LQR 0 QT die Menge der
Symbole A aus Sigma, Delta QTA ist QT, vereinigt mit Epsilon.
Und jetzt ansonsten, wenn QR und QT verschieden sind, betrachten wir
alle Wörter, für die gilt Delta QR W ist QT, ohne dass irgendein
Zwischenzustand benutzt wurde.
Also LQR 0 QT für QR ungleich QT ist ja dann nichts anderes als die
Menge der Symbole.
Längere Worte können da nicht vorkommen, weil wir keine
Zwischenzustände benutzen dürfen.
Menge der Symbole A aus Sigma, Delta QR A ist genau QT.
Ganz einfach.
Das ist sozusagen unser Induktionsanfang und nur um es mal
festzuhalten, diese Sprachen, die sind regulär.
Das sind ja einfach Vereinigungen von einelementigen Sprachen.
Die sind regulär.
Und mit denen bauen wir jetzt systematisch LQR 1 QT, LQR und so weiter
bis LQR I QT für beliebiges I.
Also nochmal die Konstruktion jetzt auch richtig zu verstehen von I
nach I plus 1.
Gucken wir uns I gleich 1 an, von 0 auf 1 sozusagen.
Also LQR 1 QT ist die Menge der Wörter aus Sigma Stern.
W überführt von QR nach QT und dabei darf nur Q1 verwendet werden.
Das heißt entweder direkt, sogar ohne Q1 zu verwenden, oder nur in
Verwendung von Q1.
Direkt, hier mal genauer aufschreiben, direkt von QR nach QT ohne
Zwischenzustand, führt uns genau die Sprache LQR 0 QT.
Das ist ja die Sprache der Wörter, die von QR nach QT führt, ohne
irgendeinen Zwischenzustand zu verwenden.
Und jetzt fisseln wir auseinander, was passiert, wenn wir von QR nach
QT kommen und dazwischen tatsächlich Q1 verwenden.
Diese 1 sagt ja, wir dürfen höchstens Q1 als Zwischenzustand.
Ja, wie sehen denn die Worte aus?
Das sind Worte, die führen uns von QR nach Q1.
Möglicherweise hängen da dran Worte, die uns von Q1 nach Q1 führen und
irgendwann geht es dann weiter direkt nach QT.
Das ist das Einzige, was passieren kann, wenn wir nur Q1 als
Zwischenzustand verwenden.
Das heißt also, LQR 0 QT ist vereinigt mit LQR 0 Q1, die Sprache, die
uns ohne Zwischenzustand von QR nach Q1 führt, mal LQ1 0 Q1 Stern, die
Sprache, die uns von Q1 nach Q1 führt, nur über Q1,
ohne Zwischenzustand, mal Q1 0 QT, die Sprache, die uns von Q1 nach QT
führt, ohne Zwischenzustand.
Das Schöne ist, die Art und Weise, wie wir die Sprache beschreiben
können, entspricht wieder einem regulären Ausdruck.
Es kommt nur Konkatenation oder Mal, also Produkt der Sprachen und
klinischer Abschluss vor.
Das heißt also, insgesamt ist dieses LQR 1 QT auch wieder regulär.
Wenn die hier alle regulär sind, von denen wissen wir das ja schon,
das war sozusagen unser Anfang.
So, und jetzt allgemein können wir also LQR I plus 1 QT nach demselben
Schema zurückführen auf LQR I, QT für beliebige Paare QR QT und
beachte, QR oder QT kann auch QI plus 1 sein.
Wenn wir hier in der Mitte einschränken, dann betrifft das nur die
Zwischenzustände.
Das heißt also, LQR I plus 1 QT können wir beschreiben als LQR I QT.
Das sind die Wörter, die von QR nach QT führen, nur unter Benutzung
von Zuständen aus Q1 bis QI.
Und die Sprache, die uns von QR nach QT führt, unter Benutzung von
zusätzlich QI plus 1.
Und die können wir aufspalten in die Sprache, die uns von QR nach QI
plus 1 führt, nur unter Benutzung von Zuständen aus Q1 bis QI.
Mal die Sprache, die uns von QI plus 1 zu QI plus 1 führt, nur unter
Benutzung von Zuständen aus Q1 bis QI.
Und davon der klinische Abschluss.
Mal die Sprache, die uns von QI plus 1 nach QT führt, nur unter
Benutzung von Q1 bis QI.
Fertig.
Das heißt also, jede dieser Sprachen für beliebiges I können wir so
beschreiben.
Und das ist eine Beschreibung, die direkt als regulärer Ausdruck
dasteht.
Das heißt also, wir haben für beliebige Zustandspaare, und die
Zustandspaare schreibe ich jetzt gar nicht mehr hin, dafür schreibe
ich hier nur so einen Punkt hier vorne und einen Punkt hier hinten
hin, jede beliebige Zustandspaare haben wir gezeigt, dass die
entsprechende Sprache, bei der nur Zwischenzustände I bis I plus 1
verwendet werden, aufgebaut werden kann durch diese Sprachen, die nur
Zwischenzustände aus Q1 bis QI verwenden, nur unter Benutzung von
Vereinigung, Produktbildung und klinischer Abschluss von Sprachen.
Das heißt also, wenn die regulär sind, dann sind die auch regulär.
Und im Prinzip haben wir hier eine Induktion gemacht.
Wir haben also per Induktion gezeigt, dass alle diese Sprachen für
alle I plus 1 zwischen 1 und N regulär sind, für beliebige
Zustandspaare, und damit gilt besonders, die sind auch regulär für die
Zustandspaare SF, F ist ein N-Zustand, und damit haben wir im Prinzip
das bewiesen, was wir beweisen wollten.
Der Beweis ist hier fertig.
Der Beweis ist algorithmisch, die Konstruktion ist nichts anderes als
dynamische Programmierung.
Wenn man die wirklich anwendet, auf einem deterministischen endlichen
Automaten, der nicht klein ist, dann ist das mühselig.
Aber das Prinzip ist ganz einfach und wenn Sie das zwei, dreimal
angewendet haben, dann werden Sie das aus dem FF können.
Wir gucken uns jetzt einfach mal ein ganz kleines Beispiel an, damit
das überschaubar bleibt.
Wir gehen von folgendem deterministischen endlichen Automaten aus.
Der Automat hat zwei Zustände, S und Q.
S ist gleichzeitig auch N-Zustand und die Übergangsfunktion ist, von S
kommt man durch Lesen von 0 oder 1 nach Q und von Q kommt man durch
Lesen von 0 oder 1 nach S.
Hier sieht man auch dem Automaten schon an, welche Sprache der
akzeptiert.
Beliebige Wörter über 0, 1, die gerade Länge haben.
Die Frage ist aber, wie können wir die jetzt durch einen regulären
Ausdruck beschreiben und vor allem die Systematik, wie können wir
diesen regulären Ausdruck systematisch aufbauen.
Wir nummerieren die Zustände durch, also die nennen wir jetzt nicht
mehr S und Q, sondern die nennen wir Q1 und Q2.
Alphabet ist 0, 1, N-Zustand ist S.
Gesucht ist also jetzt die Sprache zu dem Automat und welche ist das
nach unserer Systematik?
Das ist die Sprache der Wörter, die von Q1 nach Q1 führt, unter
Benutzung von beliebigen Zwischenzuständen.
Und da wir nur zwei haben, ist das also unter Benutzung von Zuständen
aus der Zustandsmenge Q1, Q2.
Nach unserer Schreibweise ist das nichts anderes als LQ1, 2Q1.
Also das erste Q1 steht für Startzustand, S, das zweite Q1 steht für
Endzustand, was hier jetzt auch S ist.
Und 2 steht für Q1, Q2.
Und die bauen wir von unten auf, indem wir erstmal die, wo in der
Mitte steht 0, aufbauen und dann die, wo in der Mitte steht 1.
Und darauf können wir dann LQ1, 2Q1 drauf aufbauen.
Also erstmal für beliebige Zustandspaare QI, QJ.
LQI, QJ und dazwischen darf gar kein Zwischenzustand verwendet werden.
Erstmal, wenn I und J gleich sind, dann ist das Epsilon.
Also von S nach S können wir nur durch gar nichts lesen und von Q nach
Q können wir nur durch gar nichts lesen.
Also LQI, 0QI ist Epsilon.
Und dann interessiert uns noch LQI, 0QJ.
Also wie kommen wir von QI nach QJ?
QI ist ungleich QJ.
Ohne einen Zwischenzustand, also LQI, 0QJ, IJ aus 1, 2I ungleich J.
Also wie kommen wir von da nach da ohne Zwischenzustand und wie kommen
wir von da nach da ohne Zwischenzustand?
Von da nach da ohne Zwischenzustand kommen wir durch Lesen von 0 oder
1.
Und von hier nach hier können wir auch durch Lesen von 0 oder 1.
Das heißt also LQI, 0QJ, diese Sprachen, das sind ja jetzt zwei
verschiedene, nämlich LQ1, 0Q2 und LQ2, 0Q1, sind jeweils 0 vereinigt
ein.
Reguläre Haut.
Beschreibt es einfach so.
So und jetzt geht es los mit dem Aufbauen unter Benutzung von den
Sprachen.
Erstmal für QI, QJ ist jeweils Q1, also LQ1, 1Q1.
Führen wir nach dem Schema zurück auf Sprachen, wo in der Mitte das 0
steht.
Nämlich das ist LQ1, 0Q1 vereinigt LQ1, 0Q1, LQ1, 0Q1, Stern mal LQ1,
0Q1.
So und dann müssen wir für die hier einfach nur nachgucken.
Da steht jeweils die Sprache hier oben, das ist nämlich jeweils
Epsilon.
Also das ist Epsilon, das hier und das hier bleibt Epsilon.
Das heißt also LQ1, 1Q1 ist nichts anderes als Sprache, die nur
Epsilon enthält.
Dann schauen wir das Paar IQJ an mit I gleich 1, J gleich 2.
Also die Sprache LQ1, 1Q2.
Einfach stupide zurückgeführt auf die Sprachen, wo hier eine 0 steht,
die passenden.
Dann nichts anderes als LQ1, 0Q2 vereinigt mit, wir kommen von Q1 nach
dem neuen Zwischenzustand, den wir erlauben, nämlich Q1 ohne
Zwischenzustand.
Wir kommen von dem Zustand ohne Zwischenzustand in den Zustand selber.
Wir kommen von dem Zustand ohne Zwischenzustand nach Q2.
Also das ist einfach LQ1, 0Q1 mal LQ1, 0Q1 Stern mal LQ1, 0Q2.
Und für die gucken wir einfach hier nach, hier oben.
LQ1, 0Q2 steht hier ist 0 vereinigt 1.
Dann LQ1, 0Q1 steht hier ist Epsilon.
LQ1, 0Q1 Sternchen, Epsilon Stern.
LQ1, 0Q2 sehen wir hier ist 0,1.
Also das Ganze ist die Sprache 0 vereinigt 1 vereinigt Epsilon Epsilon
Sternchen mal 0 vereinigt 1.
Das ist nichts anderes als 0 vereinigt 1.
So, dann das nächste Paar, das wir angucken.
Das nächste Paar QIQJ ist jetzt Q2Q1 und wir nehmen neu hinzu als
erlaubten Zwischenzustand Q1.
Also LQ2, 1Q1 wird genauso systematisch aufgebaut.
Das ist LQ2, 0Q1 steht hier vereinigt LQ2, 0Q1 mal LQ1, 0Q1 Epsilon
Stern mal LQ1, 0Q1 das ist Epsilon.
Das heißt also insgesamt ist das 0 vereinigt 1 vereinigt 0 vereinigt 1
mal Epsilon Stern mal Epsilon.
Das ist nichts anderes als 0 vereinigt 1.
So und jetzt das letzte mit Q1 ist neu als Zwischenzustand erlaubt.
Q2, 1 für das Zustandspaar Q2Q2.
Also LQ2, 1Q2, also erstmal von Q2 nach Q2 ohne Zwischenzustand
Epsilon, dann von Q2 nach Q1 ohne Zwischenzustand 0 vereinigt 1 mal
von Q1 nach Q1, das ist Epsilon Stern und dann von Q1 nach Q2 ist
wieder 0 vereinigt 1.
Das heißt also diese Sprache ist nichts anderes als Epsilon vereinigt
0 vereinigt 1 mal 0 vereinigt.
So und jetzt können wir zu allen möglichen Zwischenzuständen
übergehen.
Also wir erlauben zusätzlich noch Q2 als Zwischenzustand und da
brauchen wir nicht alle möglichen Sprachen zu betrachten, also nicht
alle Zustandspaare QIQJ, sondern nur das Zustandspaar, das es hier
gibt, Anfangszustand zu Endzustand.
Wir haben ja nur einen Endzustand, also ist das nur ein Zustandspaar
und da Anfangs- und Endzustand gleich ist, ist das also, und zwar Q1,
ist das also die Sprache LQ1 2Q1.
Damit die jetzt unter Benutzung von den Sprachen beschreiben können,
dann sind wir fertig, da haben wir unser L beschrieben.
So und LQ1 2Q1 ist ja nichts anderes als LQ1 1Q1 vereinigt.
LQ1 1Q2, also wir dürfen neu nach Q2 gehen, nur unter Benutzung von
Q1.
Mal, wir dürfen bei Q2 bleiben ohne Benutzung von Q2, also nur unter
Benutzung von Q1, das ist LQ2 1Q2.
Wir dürfen von Q2 nach Q1 kommen, nur unter Benutzung von Q1, das ist
LQ2 1Q1.
So und die lesen wir alle hier ab, die stehen hier irgendwo.
Das ist nichts anderes als hierfür kriegen wir Y vereinigt 0,1 mal,
hier in der Mitte haben wir 0,1 mal 0,1 in Klammern Sternchen mal 0,1.
So, wenn wir jetzt das Y da vorne mal außen vor lassen und nur das
hier angucken, das ist die Sprache von Worten, die bestehen aus 0 und
1, aber hier dürfte wegen dem 0 vereinigt 1 am Anfang und dem 0
vereinigt 1 hier 0 vereinigt 1 am Schluss das leere Wort nicht
vorkommen.
Da kommt das leere Wort nicht vor, nur das hier betrachtet.
Aber da hier vorne auch noch das leere Wort hinzukommt, können wir
diese ganze Sprache wieder schreiben als 0 vereinigt 1 mal 0 vereinigt
1 in Klammern Sternchen.
In diesem regulären Ausdruck sieht man natürlich jetzt an, dass er
genau die Worte über 0,1 beschreibt, die gerade Länge haben.
Das heißt, da muss eine 0 oder eine 1 kommen, gefolgt von nochmal
einer 0 oder einer 1 und das dann beliebig oft.
Okay, so, das schon mal jetzt zu betonen, was wir insgesamt haben im
Zusammenhang mit endlichen Automaten und regulären Sprachen.
Nochmal der Satz, die von endlichen Automaten akzeptierten Sprachen
sind genau die regulären Sprachen.
Wir haben beide Richtungen getrennt bewiesen und dieser Satz, das ist
der Satz von Klini, der ist wichtig.
Okay,
also die von endlichen Automaten akzeptierten Sprachen sind genau die
regulären Sprachen.
Da kann man jetzt die Frage stellen, was können die denn nicht, also
was ist sozusagen die Grenze dieses Berechnungsmodells endlicher
Automat?
Gibt es irgendwo Sprachen in der Welt, die von endlichen Automaten
nicht akzeptiert werden?
Ganz grundlegende Frage.
Die kann man natürlich jetzt auch anders stellen, kann man auch so
stellen, dass man sagt, gibt es nicht reguläre Sprachen?
Die Antwort ist klar, das wissen Sie auch aus GBI, die Antwort ist ja,
natürlich, endliche Automaten sind gewisserweise beschränkt.
Was wir gerne hätten, wäre ein Werkzeug, um für eine Sprache zu
beweisen, sie ist keine reguläre Sprache oder sie kann nicht von einem
endlichen Automaten erkannt werden.
Das wäre schön.
Aber erstmal vorne weggeschaltet, also was sind Sprachen, die nicht
von endlichen Automaten erkannt werden können und woran liegt das?
Wissen Sie aus GBI, dass die Sprache der korrekten Klammerausdrücke
nicht von endlichen Automaten erkannt wird?
Korrekter Klammerausdruck, naja gut, ein Ausdruck über dem Alphabet
Klammerauf, Klammerzu, der interpretiert als Klammerausdruck wirklich
korrekt ist.
Das heißt also, Sie haben zu jeder Klammerauf später auch eine
Klammerzu und Sie haben auch zu keinem Zeitpunkt mehr Klammerzu als
Klammerauf, wenn Sie von vorn nach hinten gehen.
Das sind korrekte Klammerausdrücke, das hier ist kein korrekter
Klammerausdruck, weil diese Klammerauf nicht mehr geschlossen wird,
zum Beispiel.
Das andere scheint mir in Ordnung zu sein.
Das heißt also, Klammerung ist genau korrekt, wenn erstmal gleich
viele öffnende wie schließende Klammern vorkommen, aber außerdem, wenn
man den Ausdruck von links nach rechts liest, es nie mehr Klammerzu
als Klammerauf bis dahin gibt.
So, jetzt ein endlicher Automat, der das erkennt, der muss also für
beliebig lange Ausdrücke nachhalten können, wie viele Klammern von
denen, die geöffnet wurden, sind denn schon geschlossen worden.
Das können beliebige Konstellationen sein, die sich auch im Prinzip
voneinander unterscheiden.
Der braucht also sowas wie ein unendliches Gedächtnis, unendlich
verschiedene Situationen, also echt verschiedene Situationen muss der
erkennen können.
Und das ist jetzt sozusagen die Handwaving-Argumentation, warum
endliche Automaten korrekte Klammerausdrücke nicht erkennen können,
weil endliche Automaten nur ein endliches Gedächtnis haben, Gedächtnis
sozusagen als Menge der Zustände aufgefasst.
Sie können ja umgekehrt, wenn sie so einen endlichen Automaten
angucken, sozusagen die Zustände, die sind diejenigen, die für eine
bestimmte Situation stehen, das kann man interpretieren als
Gedächtnis.
Endliche Automaten heißen endlich, weil sie nur eine endliche
Zustandsmenge haben, wenn sie aber unendlich viele verschiedene
Situationen auseinanderhalten können, sollen, dann müssen sie
unendlich viele Zustände haben.
Wie gesagt, das ist die Handwaving-Argumentation.
Und wir hätten gerne sozusagen einen Satz, ein Lemma, das wir anwenden
können, um zum Beispiel für die Sprache der korrekten Klammerausdrücke
nachzuweisen, dass sie nicht regulär ist.
Dann automatisch heißt es, dazu gibt es keinen endlichen Automaten.
Und der Satz, mit dem man das machen kann, ist das sogenannte Pumping
-Lemma.
Pumping -Lemma heißt Pumping-Lemma, Pumping für Pumpen, weil da was
vorkommt, wo Worte aufgepumpt werden.
Und wir gucken uns das Lemma mal genauer an.
Das ist so ein bisschen gewöhnungsbedürftig, aber eigentlich gar nicht
schwer, wenn man mal verstanden hat, was dahinter ist.
Das Lemma beschreibt eine Eigenschaft regulärer Sprachen.
Und zwar sagt das, sei L eine reguläre Sprache.
Wenn wir eine reguläre Sprache betrachten, dann gilt folgendes.
Dann existiert eine Zahl n, sodass für jedes Wort aus der Sprache, das
länger ist als n, eine Darstellung existiert, die so aussieht.
Jedes Wort kann hingeschrieben werden als uvx mit Anfangsteil uv, ist
nicht länger als n, Länge von uv ist kleiner gleich n, und v ungleich
leer, sodass jedes Wort, das ich bekomme, indem ich v entweder
weglasse oder beliebig oft hintereinander schreibe in der Mitte von
dem Wort, wieder in L ist.
Also, sodass auch uv hoch ix wieder in L ist, für alle i aus n null.
Also, für eine reguläre Sprache gilt, es gibt so eine Zahl n, sodass
ich jedes Wort, das länger ist als dieses n, darstellen kann als uvx,
uv ist kleiner gleich n, v ist ungleich leer, sodass uv hoch ix für
beliebiges i, also auch ux oder uv quadrat x oder uv hoch tausend x
wieder in der Sprache ist.
Also, ab einer gewissen Wortlänge sind die Worte einer regulären
Sprache so, dass sie irgendwelche Wiederholungen drin haben.
So, das beweisen wir jetzt.
Wir hatten eine reguläre Sprache.
Und jetzt benutzen wir das, was wir insgesamt bewiesen haben, dass die
regulären Sprachen genau die Automatensprachen sind.
Wir benutzen nämlich, dass es dazu einen endlichen Automaten gibt, der
die Sprache akzeptiert.
Und ich habe ja eben gesagt, diese Begrenztheit von endlichen
Automaten, die liegt daran, dass sie eine endliche Anzahl von
Zuständen haben.
Das heißt, wenn Worte abgearbeitet werden, können von einem Automaten,
aber beliebig lang werden können, dann muss da irgendwas immer wieder
durchlaufen werden in dem Automaten.
Das hier bezieht sich auf Wörter, die sehr lang werden, Länge haben,
die größer als n sind.
Wenn wir jetzt das n für unseren Beweis suchen, dann werden wir
wahrscheinlich da irgendwo im Umfeld der Anzahl der Zustände unseres
Automaten fündig.
Der Satz ist genau so formuliert, dass wir mit n gleich Anzahl der
Zustände des Automaten prima hinkommen.
Unsere Sprache ist regulär, unsere Ausgangssprache.
Wir nehmen einfach den zugehörigen endlichen Automaten her und sagen,
wir definieren schon mal das n, das es hier nach dem Satz geben soll,
als Anzahl der Zustände des Automaten.
Und jetzt gucken wir irgend so ein Wort an, aus unserer regulären
Sprache, das länger ist als n.
Wir gucken so ein w an, Länge von w größer n.
Das w sieht dann irgendwie so aus, a1 und so weiter, an und so weiter
bis am.
Das ist so ein a1 bis am, m echt größer als n.
Das n-te Symbol ist hier irgendwo.
Und jetzt gucken wir uns mal an, was passiert, wenn unser endlicher
Automat dieses Wort abarbeitet.
Also das Wort hat eine Länge größer n, das sieht so aus, a1 bis am.
Das heißt, wenn der Automat das Wort abarbeitet, dann werden
irgendwelche Zwischenzustände oder Zustände q0 bis qm durchlaufen,
wobei diese Zustände nicht alle verschieden sind.
Die können sogar nicht alle verschieden sein, weil m größer n ist.
Das heißt, irgendwo, und wenn das Wort akzeptiert wird, dann ist das
qm insbesondere in f.
Aber wenn das m größer als n ist, dann muss also irgendwo mal ein
Zustand zum ersten Mal wieder durchlaufen werden.
Also irgendwann kommen wir zum Zustand wieder zurück.
Gucken wir uns einfach mal so eine Situation an.
Das sind also jetzt Zustände qi, qj in dieser Folge, die aber
eigentlich gleich sind.
Die Indizes i und j sind verschieden, entsprechend der Nummerierung
hier dieser Zustandsfolge, aber qi und qj sind dasselbe.
Und ob der a soll i kleiner als j sein.
Das heißt also, bei Abarbeitung von b gleich a1 bis am geht es
irgendwann mal so, dass wir hier nach qi kommen.
Aber nachdem wir a1 bis ai gelesen haben und dann wird ai plus 1
gelesen und so weiter und so fort.
Irgendwann mal kommen wir wieder zu qi zurück.
Das qj ist gerade wieder hier qi.
Und dann geht es weiter, hier fehlen ein paar Pünktchen.
Nicht nur zwei Übergänge, hier fehlen ein paar Pünktchen und dann geht
es nach qm.
Also insbesondere wissen wir aber, wenn wir so ein langes Wort haben,
das länger ist als die Anzahl der Zustände des Automaten, dann muss
bei der Abarbeitung so ein Kreis in dem Automat durchlaufen werden.
Einfach die Zustandsfolge, die durchlaufen.
So hintereinander und so.
Okay, wenn aber bei Abarbeitung von w dieser Kreis durchlaufen wird,
bevor wir schließlich in einem Endzustand landen, dann können wir auch
mit einem Wort in den Endzustand kommen, das diesen Kreis nicht
durchläuft, das einfach hier schnurstracks durchgeht.
Oder bei dem dieser Kreis zweimal durchlaufen wird, einmal oder
viermal.
Das ist ja genau das, was dieses Lemma sagt, man kann dieses w
irgendwie aufteilen in uvx und insbesondere ist uv kleiner gleich n,
sodass auch uv hoch ix wieder in der Sprache ist.
Die Aufteilung, die können wir hier ablesen.
Mit u kommen wir hier hin, nach qi, von s nach qi.
Mit v kommen wir hier durch und mit x kommen wir dann von ui dahin.
Und natürlich muss diese Wiederholung spätestens beim enden Zustand
vorkommen.
Das heißt also uv hat eine Länge kleiner gleich n.
Und dieser Zykel existiert, das heißt v ist ungleich leer.
Das heißt also aus dieser Abarbeitung von w können wir die Aufteilung
ablesen.
Hier steht nochmal, da muss es so einen Zykel geben.
Den können wir auch weglassen oder mehrfach durchlaufen, dann kommen
wir trotzdem nach qm.
Das heißt also, wir können das w zerlegen in a1 bis ai, den Teil der
abgearbeitet wird, bevor wir zu diesem qi kommen.
Das ist u, gefolgt von dem Teil ai plus 1 bis aj.
Das ist der Teil, der abgearbeitet wird, indem man durch den Zykel
geht.
Das ist v und das ist insbesondere ungleich leer.
Dann muss es einen Zykel geben bei der Abarbeitung von w.
Gefolgt von dem Rest, aj plus 1 bis am.
Und wenn das Wort abgearbeitet werden kann, dann kann auch uv hoch ix
abgearbeitet werden.
Die aus n0 Abarbeitung.
Wenn Sie sich das einprägen und was dahinter ist, dann können Sie sich
den Satz auch merken.
Ich gebe zu, erst mal ein bisschen gewöhnungsbedürftig, dieser Satz
oder das Pampim Lema, wenn man das anwenden will, sollte man das aber
so richtig parat haben.
Und das kriegen Sie in den Kopf rein, indem Sie sich immer dieses
Bildchen vorstellen.
Ja,
da kann es auch mehr Zykel geben.
Das ist ja auch nur eine Aussage, es existiert ein n.
Und es existiert für jedes Wort der Länge n so eine Darstellung.
Da kann es auch mehrere Darstellungen geben, wo an mehreren Stellen
aufgeblasen wird.
Das ist ja nur eine Existenzaussage für den.
Was wir jetzt noch machen wollen, ist dieses Lema anwenden.
Gewinnbringend anwenden, sage ich mal.
Also das Lema ist eine Aussage über reguläre Sprachen.
Wenn die Sprache regulär ist, dann erfüllt sie dieses Lema.
Wie kann man so einen Satz verwenden?
Das Blöde ist, das ist nur ein Satz, der nur eine notwendige Bedingung
für regulär beinhaltet.
Wenn eine Sprache diese Bedingung nicht erfüllt, dann ist eins
glasklar.
Die Sprache ist nicht regulär.
Dafür kann man es verwenden, das Lema.
Aber ich warne, da eben diese Eigenschaft, es gibt ein n, so dass für
jedes Wort der Länge größer n es eine Darstellung gibt, als u, v, x,
v, kleiner gleich n, v, ungleich epsilon, so dass u, v hoch i, L ist
für alle i.
Das kann auch zutreffen für Sprachen, die nicht regulär sind.
Das ist nicht hinreichend.
Das heißt also, wenn Sie so eine Sprache hernehmen, den Verdacht
haben, die ist nicht regulär, können Sie es vielleicht mit dem Pumping
Lema beweisen.
Vielleicht haben Sie auch Pech und diese Sprache ist zwar nicht
regulär, erfüllt aber das Pumping Lema.
Jetzt wollen wir mal einfach so anwenden, üben.
Erstes Beispiel.
Das erste Beispiel ist harmlos.
Da gucken wir uns nämlich eine reguläre Sprache an, von der wir ja
wissen, dass sie das Pumping Lema erfüllt, denn das haben wir ja
gerade bewiesen.
Ich habe schön immer das Pumping Lema nochmal in voller
Ausführlichkeit hier stehen.
Also wir gucken uns die Sprache an, L.
L enthält alle Wörter aus 0,1 Sternen oder über 0,1, für die gilt, W
enthält 1, 0 nicht als Teilwort.
Die Sprache hatten wir in der allerersten Vorlesung schon als ein
Beispiel und da haben wir schon sofort gesehen, ja, die ist regulär
oder dazu gibt es einen endlichen Automaten.
Enthält 1, 0 nicht als Teilwort, heißt ja nichts anderes als nach der
ersten 1 darf keine 0 mehr kommen.
Das kann man beschreiben als 0 Stern, 1 Stern.
Da können beliebig viele Nullen kommen, aber wenn dann irgendwann mal
eine 1 kommt, dann darf keine 0 mehr kommen.
0 Stern, 1 Stern.
Das ist regulär.
Das heißt also, die muss das Pumping Lema erfüllen und das ist auch
irgendwie klar.
Ich muss einfach jetzt irgendwie nur so ein N angeben, sodass für
jedes Wort, das länger ist als dieses N, ich so eine Darstellung, uvx,
angeben kann mit uv kleiner gleich n, v und gleich y, sodass auch uvx
für jedes i in L ist.
Und ich gebe hier einfach mal n gleich 1 an.
Die Darstellung ist w gleich uvx und ich sage einfach und bei der
Darstellung ist u gleich y.
Es muss ja nur eine Darstellung geben.
Dann entspricht v also dem allerersten Buchstaben von w.
Wenn ich sage, b soll länger als 1 sein, eine Länge haben, die länger
als 1 ist, also nicht leer sein heißt das insbesondere, und u bei der
Darstellung von w als uvx soll u leer sein.
Das ist ja nichts anderes als v ist der erste Buchstabe von b.
Wenn jetzt b1,0 nicht als Teilwort enthält, dann kann ich auch den
ersten Buchstaben weglassen oder den ersten Buchstaben tausendmal
hinschreiben.
Dadurch kann kein 1,0 entstehen.
Das da vorne ist entweder eine 0, die kann ich auch weglassen oder
beliebig oft wiederholen.
Dadurch kommt da kein 1,0 rein.
Oder das erste ist eine 1.
Dann ist aber dieses ganze w nur eine Folge von Einsen.
Da kann ich auch diese 1 nochmal x-mal wiederholen oder weglassen.
Dadurch kommt wieder kein 1,0 als Teilwort.
Okay, also hier haben wir nur verifiziert, dass eine reguläre Sprache
das erfüllt, was sie, nachdem wir es bewiesen haben, erfüllen soll.
Die Aussage ist pumping lemma.
Hier wird es jetzt interessanter.
Können wir mit dem pumping lemma zeigen, dass die Sprache der
korrekten Klammerausdrücke nicht regulär ist?
Ja.
Können wir sogar für eine speziellere Sprache zeigen können, dass sie
nicht regulär ist.
Nämlich die Sprache der Wörter, die so aussehen, 0 hoch i, 1 hoch i.
Für beliebiges i.
Also eine Anzahl von Nullen gefolgt von genau derselben Anzahl von
Einsen.
Sie erinnern sich, in der ersten Vorlesung hatten wir ja am Schluss
kontextfreie Grammatiken.
Da haben wir eine Grammatik angegeben,
über die diese Sprache erzeugt wird.
Und da habe ich so gesagt, naja, also ist die Sprache L gleich Menge
aller Wörter.
Wörter hat die Form 0 hoch N, 1 hoch N, für beliebiges N, ist ja wohl
regulär.
Oder, ich weiß nicht, ob Sie es mitgekriegt haben, da haben wir da
Zweifel und das offengelassen.
Wenn Sie jetzt wirklich da aufgepasst haben und dann Ihr Zweifel Sie
jetzt zwei Wochen lang beschäftigt hat, also jetzt wird es aufgelöst,
die Sprache ist nicht regulär.
Und das können wir zeigen.
Wir wählen, wir betrachten beliebiges N.
Ah, das vielleicht jetzt nochmal genauer.
Wenn wir das Pumping Lemma benutzen, um für eine Sprache zu zeigen,
sie ist nicht regulär, dann müssen wir hier hinten die Negation
zeigen.
Also die Sprache darf das nicht erfüllen.
Das muss also gelten, für alle N gibt es ein Wort, oder gibt es ein
Wort, das länger ist als N.
Sodass für jede beliebige Darstellung des Wortes als uvx mit uv,
kleiner gleich N, v, epsilon, als ein i gibt, sodass uv hoch ix nicht
in L ist.
Das ist die Negation von dem da hinten.
Nehmen wir also ein beliebiges N und jetzt ein Wort w, das länger ist
als N und nur eins zu nehmen, was sozusagen hier zum Widerspruch führt
zu dieser Eigenschaft hier.
Dafür nehmen wir 0 hoch N, 1 hoch N.
Dieses w ist größer N.
Und jetzt gucken wir jede beliebige Darstellung von dem w als uvx mit
uv, kleiner gleich N, v und gleich epsilon an.
Wenn uv eine Länge hat, die kleiner gleich N ist, dann ist das uv hier
in dem vorderen Teil zu finden.
Also uv besteht nur aus Nullen.
Und das ist der Trick.
Wenn das v und gleich leer ist, wenn wir das weglassen,
beispielsweise, haben wir nicht mehr die Anzahl von Nullen gefolgt von
derselben Anzahl von Einsen.
Dann haben wir plötzlich eine Null weniger.
Nicht mehr in der Sprache.
Also für jede Darstellung von diesem w als uvx mit uv, kleiner gleich
N gilt, und v und gleich epsilon gilt.
Wenn ich das v weglasse, kriege ich 0 hoch L, 1 hoch N, L kleiner N.
Das ist nicht mehr ein Wort aus dieser Sprache.
So.
Das ist die Art und Weise, wie Sie am häufigsten das Pumping Lemma
anwenden werden sollten.
Denn das ist eine Anwendung, die einem wirklich einen Wissensgewinn
bringt.
Sie haben eine Sprache, Sie vermuten, die ist nicht regulär, damit
können Sie zeigen, sie ist nicht regulär.
Wenn Sie so einen Beweis führen können.
Aber meine Warnung war ja, das wird nicht immer hinhauen.
Es gibt nicht reguläre Sprachen, die erfüllen das Pumping Lemma.
Und dafür habe ich jetzt das dritte Beispiel.
Eine Sprache, der sieht man eigentlich sofort an, die kann nicht
regulär sein.
Aber unverschämterweise erfüllt sie unser Pumping Lemma.
Und das ist folgende.
Sprache der Wörter w aus Sigma Stern.
W hat entweder die Form, das sind K1, also W gleich 1 hoch K, K größer
0.
Oder es hat die Form, das sind J0, gefolgt von einer quadratischen
Anzahl von Einsen.
Quadratische Anzahl von Einsen, den endlichen Automat will ich sehen,
der das erkennen kann.
Der Punkt.
Also, Menge der Wörter über 0,1.
W ist entweder 1 hoch K, K größer 0.
Oder W ist 0 hoch J, 1 hoch K Quadrat.
J größer gleich 1, K größer gleich 0.
Also hier quadratische Anzahl von Einsen.
So.
Die Sprache erfüllt das Pumping Lemma.
Für das Pumping Lemma müssen wir ja nur ein N angeben, sodass für
jedes Wort der Größe der Länge länger als N so eine Aufteilung gibt.
X.
Sodass UV hoch IX für alle I wieder in der Sprache ist.
Und hier kann ich so ein N angeben, nämlich N gleich 1.
Wenn ich jetzt so ein Wort aus L betrachte, ein beliebiges Wort aus L,
das länger ist als 1, dann kann ich dafür so eine Darstellung als UVX
angeben mit UV kleiner gleich N und V ungleich Y.
Nämlich Sätze U gleich Y und Länge von V gleich 1.
Einzige Möglichkeit.
Länge von V gleich 1.
Das heißt also, V ist das erste Symbol.
So, und dann gucke ich jetzt an und was passiert, wenn ich jetzt
dieses erste Symbol weglasse oder beliebig oft wiederhole.
Es gibt jetzt zwei Fälle, wie das W aussehen kann und was das heißen
kann.
Das W kann so ein 1 hoch K sein.
Naja gut, wenn ich jetzt die erste 1 von 1 hoch K weglasse oder
beliebig oft wiederhole, kommt ein 1 hoch L raus.
Das ist wieder ein Wort aus L.
Oder B hat so eine Form 0 hoch J, 1 hoch K Quadrat.
J ist aber wohlgemerkt größer gleich 1.
Das heißt, das erste Symbol ist so eine 0.
Wenn ich jetzt die 0 weglasse oder ein paar 0 mehr dazu schreibe,
tangiert das den kritischen Teil, dass hinten die Anzahl der Einsen
quadratisch sein, Quadratzahl sein muss.
Überhaupt nicht.
Das heißt, in anderen Worten, wenn ich dann so ein W gleich 0 hoch J,
1 hoch K Quadrat betrachte und unser V ist das erste Symbol, dann ist
auch U V hoch 0 X in L beziehungsweise U V hoch I, I größer gleich 1 X
in L.
Denn in dem ersten Fall, naja gut, dann fällt halt einfach die
Vorrunde 0 weg.
Das ist nicht schlimm.
Das ist selbst dann nicht schlimm, wenn es nur eine führende 0 gab.
Da bleibt immer noch 1 hoch K Quadrat übrig.
Und 1 hoch K Quadrat ist ein Wort von dem Muster.
Oder aber da kommen noch so ein paar Nullen dazu, wenn I größer gleich
1 ist, aber das tangiert hinten die Eins quadratisch.
Das heißt also, diese Sprache hier sieht so gar nicht regulär aus, ist
auch nicht regulär, erfüllt aber das Pumping-Lemma.
Die Welt ist schlecht, aber so schlecht ist sie doch nicht.
Zumindest für die Sprache haben wir noch ein allgemeineres Pumping
-Lemma, mit dem man zeigen kann, die Sprache ist nicht regulär.
Aber auch dies verallgemeinerte Pumping-Lemma, das wir das nächste Mal
dann genauer betrachten, das sieht halt dann noch schwieriger aus als
das hier.
Auch dieses verallgemeinerte Pumping-Lemma beschreibt nur eine
notwendige Bedingung für Regularität, keine hinreichende, hat also
auch irgendwo dann Grenzen.
Ja, und das wär's für heute.