Ich begrüße Sie zur Fortsetzung der Vorlesung der Grundlageninformatik
II.
Vorige Woche war ich ja nicht hier, da habe ich mich von Mostagim
vertreten.
Und ich habe hier schon die erste Frage gekriegt, wie war Singapur?
War sehr interessant, ist also ein sehr aufstrebender Ort, sehr
unheimlich beeindruckend, was dort alles entsteht, wie strategisch
unterwegs sind.
Und deren wesentliches Thema ist eben der Bereich Services, IKT, das
ist ein Bereich Mikroelektronik, das sind Dinge, wo die sehr aktiv
sein wollen.
Zukünftige Dienstleistungen ist für die ein ganz wichtiges Thema.
Und ich war da im Zusammenhang mit Elektromobilität, auch da sind die
sehr interessant unterwegs, wobei man dort genauso wenig
Elektrofahrzeuge sieht wie bei uns, aber die sind dabei, das zu
ändern.
Wir sind da auch dabei, mal sehen, wie sich das weiterentwickelt, ein
sehr interessanter Standort.
Ich habe da auch interessanterweise einen meiner Bachelor
-Abschlussarbeiter getroffen, der gerade ein Praktikum dort macht,
auch ein interessantes Thema für Studierende, die ihr Praktikum im
Ausland machen wollen.
Da gibt es halt viele Unternehmen, die so etwas, das wollte ich jetzt
nicht hier machen, die halt im Bereich der neuen Technologien
unterwegs sind und dort auch Studenten für Praktika aufnehmen.
Ich denke, das habe ich beantwortet.
Jetzt kommen wir zum Thema Grundlageninformatik II.
Also, letztes Mal hat Frau Mostergiem Ihnen hier einiges schon erzählt
oder weitergemacht beim Thema endliche Automaten.
Wir hatten ja schon einiges uns angeschaut.
Ich gehe hier nochmal ganz kurz durch.
Sie wissen, was ein Automat ist.
Wir hatten Miliautomaten angeschaut, hatten uns die Zustandstafeln,
Zustandsdiagrammen angeschaut.
Ich hatte Ihnen Beispiele gegeben.
Das war dieses Tiefgaragentor, der Warenautomat.
Und dann hatten wir noch die Vizereal-Edition betrachtet, einen
einfachen PC.
Ich hatte Ihnen was zur Größenordnung erzählt.
Dann hat Frau Mostergiem weitergemacht mit einigen weiteren Dingen.
Hat Ihnen was über Murautomat erzählt.
Hat Ihnen diese Ampelsteuerung nochmal gezeigt, die ich zu Anfang
schon drin hatte.
Also nochmal kurz zurück hier mit diesen fünf Zuständen und gezeigt,
wie das hier zustande kommt, wie das funktioniert.
Und dann ging es um Akzeptoren und in dem Zusammenhang also Automaten,
die man nimmt, um Entscheidungen zu treffen in Bezug darauf, ob man
ein Wort akzeptiert oder nicht.
Ob also am Ende die Fahne geschwenkt wird, das Ding ist richtig, das
Wort wird akzeptiert, oder ob da eben keine Fahne geschwenkt wird,
wenn ich also sage Endzustand, dann heißt das im Prinzip, ich habe die
Ausgabe, ich kann auch sagen, das ist ein Automaten mit Ausgabe, der
einfach bei einigen Zuständen eine Fahne schwenkt und bei anderen
nicht.
Und da, wo er die Fahne schwenkt oder ein grünes Licht macht, da habe
ich halt einen Endzustand.
Also das ist einfach die Vereinfachung.
Ich betrachte jetzt Endzustände und andere Zustände.
Und das gucke ich mir an, wie ist das Verhalten der Automaten in Bezug
auf das Akzeptieren von Wörtern, die auf dem Eingabeband stehen.
Ich starte im Anfangszustand, schreibe ein Wort aus Eingabeband und
schaue mir an, was passiert oder in welchem Zustand bin ich, wenn ich
das Wort vollständig eingelesen habe.
Das ist das, was ich mir angucke.
Und dann gibt es halt hier die Arbeitsweise, es gibt wieder hier die
Art, wie ich es darstelle.
Und dann gibt es einen wichtigen Begriff, der Ihnen mehrfach
auftauchen wird bei all den verschiedenen Automaten, die wir
betrachten, der Begriff der Konfiguration.
Und das ist halt, Konfiguration ist halt die Information, die ich
brauche, um aus der aktuellen Situation eines solchen Akzeptors
weitermachen zu können, also genau feststellen zu können, wie wird
dieser Prozess weitergehen, wie wird also jetzt der Automat das noch
auf dem Band befindliche Wort bearbeiten können, bis er irgendwann
einmal hält.
Also Konfiguration ist die Information, die ich brauche, um sagen zu
können, was der Automat tatsächlich weitermachen wird, wie das
Verhalten des Automaten weiterhin bestimmt sein wird.
Das steckt da im Prinzip drin, wobei wir die Übergangsfunktion
natürlich im Hintergrund haben, aber ich muss eben sehen, was ist der
aktuelle Zustand, was ist das Restwort auf dem Eingabeband.
Das sind die beiden Dinge.
Der Zustand, wie ist also hier bei den internen Zustanden die aktuelle
Situation und was steht ab der aktuellen Leseposition noch auf dem
Band drauf, was noch zu verarbeiten ist, dann kann ich das weitere
Verhalten des Automaten damit vollständig bearbeiten, sofern ich auch
das Übergangsverhalten oder die Übergangsdefinition, die
Zustandsübergangsfunktion, kenne.
Das war die Konfiguration.
Dann kann ich sagen, wie ich von einer Konfiguration in die nächste
übergehe.
Da waren eine Reihe Beispiele gemacht worden anhand eines sehr
einfachen Automaten.
Und dann wurde hier noch ein Beispiel gebracht, wie ich also zu einer
bestimmten Menge dann einen Automaten konstruiere oder einen Akzeptor
konstruiere, der genau dieses Wort oder diese Sprache akzeptiert.
Jetzt ganz kurz hier, können Sie bitte die Folien im Vollbildmodus
präsentieren, danke.
Das mache ich gleich, mache ich ab dem Augenblick, wo ich anfange mit
neuen Dingen.
Wiederholung mache ich immer nur in diesem Modus, also ich kann es
etwas größer machen, weil ich den Animationsbereich nicht brauche,
aber ich gehe in dem Augenblick in den normalen Modus rein, wenn ich
wieder anfange, etwas Neues zu tun.
Das ist hier der...
Ups, nochmal hier rauf.
Das ist halt nur Wiederholung im Augenblick.
So, das war die Art, wie ich also einen Automaten konstruiere, der
eine konkrete Sprache akzeptiert.
Dann kam als nächstes die Frage, ob man eigentlich das mehrere Wort in
einer Sprache haben kann, wie das aussieht mit endlichen Mengen, ob
die von endlichen Automaten akzeptiert werden können.
Das sind alles relativ einfache Fragen.
Und dann kam hier nochmal ein kleineres Beispiel.
Und dann kam eine wichtige Fragestellung, nämlich die Frage, ob man
eigentlich jede Sprache akzeptieren kann durch einen endlichen
Automaten.
Und da war eben das Wichtige dieses Bild, wo man versucht hat, diese
Sprache A hoch N, B hoch N, ich könnte auch sagen, eine
Klammersprache, bei der ich öffnende und schließende Klammern habe, ob
ich eine solche Sprache akzeptieren kann.
Und warum ist diese Sprache interessant?
Weil wir zu Anfang der Vorlesung uns eine Frage gestellt haben, welche
Art formalen Modellen brauchen wir, um eine ausreichende
Ausdrucksfähigkeit gewährleisten zu können für die Dinge, die wir in
Programmiersprachen darstellen wollen.
Und so eine einfache Klammerstruktur, öffnende und schließende
Klammern, tauchen nun wirklich in vielfältiger Form in
Programmiersprachen auf, zum Beispiel in arithmetischen Ausdrücken,
aber auch in anderen Strukturen, wenn wir uns aus einem Programm in
ein Unterprogramm hineinbewegen und dort wieder in ein Unterprogramm
und Ähnliches.
Geschachtete Strukturen sind typisch für programmiersprachliche
Konstrukte.
So etwas müssen wir auf jeden Fall darstellen können.
Und hier ist angedeutet, auf diese Abstraktion, dass man einfach sagt
A's und B's, ich hätte auch sagen können, öffnende und schließende
Klammern, aber A und B ist jetzt hier vielleicht etwas instruktiver.
Also das ist einfach, zeigt einfach, wir müssen im Prinzip zählen
können, wie viele A's hier gekommen sind, damit wir anschließend
feststellen können, ob genügend B's hinterherkommen.
Und mit endlichen Automaten ist halt das Zählen nicht so einfach, wie
wir hier sehen.
Und wir können eben zeigen, dass das tatsächlich auch richtig
schwierig ist.
Ich soll das Licht ausschalten, Herr Kochanek, diese Aufgabe übergebe
ich Ihnen.
Hier steht, könnten Sie bitte vorne das Licht ausschalten, die Folien
sind viel zu hell und nur schwer zu erkennen.
Bitte, viel Spaß mit der Haustechnik.
Ich mache lieber weiter.
Und dann kam darauf dann eine wichtige Überlegung, die, jetzt habe ich
das noch beantwortet, das habe ich eigentlich schon beantwortet, das
ist damit erledigt, jetzt kommt als nächstes eine wichtige Sache,
nämlich das Pumping-Lemmer für endliche Automaten, beziehungsweise für
Sprachen, die von endlichen Automaten akzeptiert werden.
Und das ist eine ganz wesentliche Erkenntnis, ich gehe gleich ins
Präsentationsmodus, weil gleich was Neues kommt, aber hier noch nicht.
Dieses ist eine ganz wichtige Erkenntnis, dieses Pumping-Lemmer
präsentiert Ihnen eine Überlegung, die Sie an vielen Stellen finden,
wenn es darum geht, die reale Welt zu modellieren.
In dem Augenblick, wo ich irgendetwas modelliere, dadurch, dass ich
sage, ich habe irgendeinen Zustand oder ich habe irgendeinen Prozess,
und bei dem Prozess kann ich im Prinzip nur endlich viele
unterschiedliche Situationen unterscheiden.
Nur 27 oder 356 oder 1.526.000.
Wenn ich ein Gerät habe, mit dem ich aufgrund von Einschränkungen, die
technisch bedingt sein können, nicht in der Lage bin, beliebig viele
Situationen zu unterscheiden, sondern nur endlich viele, dafür sagen
wir normalerweise N verschiedene abstrakt, wenn das eingeschränkt ist,
und ich betrachte einen Prozess, der also beliebig lang ist, und ich
weiß, ich kann nur 17 verschiedene Situationen unterscheiden, dann
weiß ich, dass in einer Folge, die hier angedeutet, die länger ist als
in dem Fall 17, diese verschiedenen Situationen, die dort auftreten,
nicht alle verschieden sein können, sondern es muss mindestens eine
Situation doppelt aufgetreten sein.
Das ist die wesentliche Erkenntnis.
Ein Prozess, der beliebig lang ist, bei dem ich nur endlich viele
Situationen unterscheiden kann, wird in dem Augenblick, wo der Prozess
länger ist als die Anzahl dieser verschiedenen Situationen, mindestens
eine Situation haben, die doppelt auftaucht.
So, und wenn ich das erkannt habe, dann weiß ich, es gibt zwei
Positionen, das sind die beiden, die hier angedeutet sind, ich gehe
jetzt doch in Präsentationsmodus über, weil das jetzt einfacher ist
für mich.
Also das ist hier die wesentliche Erkenntnis.
Hier ist diese Situation, da muss ich erstmal umschalten in
Stiftmodus, da ist die Situation, zwei Situationen sind identisch.
Und dann weiß ich etwas, dass es eine gewisse Anfangshistorie gibt,
bis ich da hingekommen bin, dann gibt es irgendetwas, was zwischendrin
passiert ist, bis ich wieder die gleiche Situation habe, wie die, die
ich vorher schon mal gesehen hatte, und dann geht das irgendwie
weiter.
Und die Anfangssituation bezeichne ich mit X, die Situation, um wieder
zu dem gleichen Situation zurückzukommen, mit Y, und das, was dahinter
folgt noch irgendwann, das ist das Z.
Und die wesentliche Erkenntnis ist, wenn ich nochmal einen langen
Prozess habe, irgendeinen ganz langen Prozess, und ich weiß, ich habe
nur eine begrenzte Anzahl von unterschiedlichen Situationen, meine N
-Situationen, die ich unterscheiden kann, sobald ich mehr Situationen
habe als diese N, muss eine doppelt aufgetaucht sein.
Und in dem Augenblick weiß ich, dass ich, wenn ich hier hinten bin,
kann ich gar nicht wissen, wie oft dieses Y hier aufgetaucht ist.
Ob das gar nicht da war, ob das einmal durchlaufen wurde, ob das
mehrfach durchlaufen wurde, das weiß ich ja nicht mehr.
Ich weiß hier an dieser Stelle nur genau das Gleiche wie an der
Stelle.
Das ist der interne Zustand.
Und in dem Augenblick, wenn ich das so weiß, kann ich Aussagen machen
über die Struktur von solchen Prozessen, auf Basis der Modellierung,
die ich gemacht habe.
Das beobachten wir jetzt an dem ganz einfachen Beispiel eines
endlichen Automaten, der 17 Zustände hat oder N Zustände, das heißt,
sobald ich N plus 1 Zustände beobachtet habe, sind zwei davon
identisch.
Und genau das steht hier drin.
Automat mit N Zuständen, dann ist für jeden ausreichend langen
Prozess, nämlich für jedes Wort, das mindestens N Zeichen enthält,
eine solche Zerlegung möglich, weil ich nach einem Anfangsstück der
Länge N, habe ich ja angefangen mit dem Anfangszustand S0 und dann
irgendwelche Folgezustände, jeweils ein Folgezustand, habe ich nach
Einlesen von N Zeichen N plus 1 Zustände betrachtet.
Und es ist dazwischen wirklich etwas passiert, ich bin also nicht in
einem Zustand geblieben, sondern ich habe wirklich etwas eingegeben.
Also das Y ist wirklich disassiert, dieser Bereich ist wirklich nicht
leer.
Dann weiß ich, das, was dort als Y bezeichnet ist, kann ich beliebig
oft machen und es hat keine Auswirkung darauf, in welchem Zustand ich
am Ende gelangt sein werde.
Das heißt, das Akzeptierungsverhalten meines Automaten wird nicht
dadurch beeinflusst, wie oft das Y durchlaufen wird.
Und damit weiß ich etwas über die Struktur der Sprachen, die von
endlichen Automaten akzeptiert werden.
Beziehungsweise, wenn ich eine Sprache habe, bei der für solche Wörter
ausreichend der Länge dieses nicht auftaucht, der nicht so ist, dann
ist das offensichtlich eine Sprache, die nicht von endlichen Automaten
akzeptiert werden kann.
Und das ist das, was auf der übernächsten Folie steht.
Hier steht vieles annotiert, das ist also das, was da bewiesen wird,
das haben wir letztes Mal gesehen, hat Frau Mostagy Ihnen erklärt.
Im Prinzip ist es eben das hier, das wesentliche Bild.
Das müssen Sie sich merken.
Hier fehlt übrigens noch ein Y dran.
X, Y, Z.
Ja, Sie haben ein Anfangsstück, Sie gehen durch eine Schleife durch
und dann haben Sie ein Endstück.
Und das, was hier hinten passiert, oder das, was Sie dort wissen über
das Akzeptierungsverhalten des Automaten, ist unabhängig davon, wie
oft das Y durchlaufen wurde.
Das ist die wesentliche Struktur.
Ein endliches System kann nur endlich viele Situationen unterscheiden
und sobald Sie mehr als diese Situation zu betrachten haben, haben Sie
Wiederholungen.
Ich betone das so sehr, weil Ihnen das nicht nur einmal begegnend
wird, sondern auch öfter.
Aber eigentlich brauchen Sie es nur jetzt einmal zu verstehen.
Und dann können Sie das für jeden anderen Prozess, bei dem das genauso
auftaucht, auch genauso wieder anwenden.
Die Prozesse können komplizierter sein, nicht so einfach wie hier nur
Folge von Zuständen und ich gehe mit Eingabesymbolen von einem auf den
nächsten Zustand über.
Das kann komplizierter aussehen, wir werden das später sehen bei den
kontextfreien Sprachen, da werden wir etwas kompliziertere Strukturen
betrachten, bei denen wir aber im Grunde genommen einfach nur das hier
nochmal anwenden, nur in einer etwas komplexeren Form.
Das ist das Pumping Level.
Eine ganz wichtige, elementar wichtige Erkenntnis über das Verhalten
von endlichen Systemen und Möglichkeiten, über ihr Verhalten zu
argumentieren.
Okay, das ist das, was hier beschrieben wurde.
Dann gibt es hier diese schönen Beispiele.
Und jetzt, das war die letzte Folie vom vorigen Mal, und ich
wiederhole das jetzt hier so intensiv, weil das einfach wirklich eine
ganz wesentliche Erkenntnis ist, jetzt schon in der vierten Vorlesung
oder dritten Vorlesung letztes Mal, das Pumping Lemma ist hier unten
nochmal formuliert und hier oben drüber steht es nochmal.
Jedes Mal steht es nur Folgerung 1 drauf.
Und der einzige Unterschied ist, dass wir hier bei der Folgerung 1
eine Aussage formulieren, die äquivalent ist zum Pumping Lemma, aber
eben das Pumping Lemma in der umgekehrten Art und Weise darstellt,
nämlich in der Kontrapositionsform.
Hier steht das Pumping Lemma in der Form A folgt B.
A ist, wenn L die Sprache eines endlichen Automaten ist, dann gibt es
ein N aus N, sodass es für jedes Wort, wie mit W N, eine Zerlegung
gibt, für die gilt diese drei Eigenschaften.
Umgekehrt heißt das, ich habe irgendeine Sprache und ich nehme mir ein
beliebiges N her, wenn also für jedes N, das, was hier als B stand,
muss ich negieren, nicht B.
Hier steht, es gibt ein N, dann muss ich jetzt sagen, für jedes N gibt
es ein Wort, W größer gleich N, sodass es für jede Zerlegung, vorher
stand da, es gibt ein Wort, ich kann mir vorstellen, dass für jedes
Wort gibt es eine Zerlegung.
Jetzt sagen wir, es gibt ein Wort, sodass für jede Zerlegung mit
diesen Eigenschaften, diesen beiden Eigenschaften, ein I aus N0 gibt,
mindestens ein, sodass das XY hoch IZ nicht aus L ist.
Das L ist dadurch die Annotation verdeckt.
Wenn das der Fall ist, das ist jetzt die Aussage nicht B, für jedes N
gibt es ein Wort einer gewissen Länge, größer gleich N, sodass für
jede Zerlegung mit den Eigenschaften, dass das Anfangsstück XY mit Y
größer gleich 1, also die Länge XY kleiner als N, Y größer gleich 1,
mindestens ein Zeichen, ein I0 gibt mit XY hoch IZ nicht aus L, das
ist nicht B, dann ist L nicht Sprache eines endlichen Automaten.
Warum braucht man das, diese Aussage?
Weil ich mit dieser Aussage hier unten, mit dem Pumping-Lemma, noch
nicht so sehr viel anfangen kann.
Die Aussage des Pumping-Lemmas heißt zunächst mal nur, wenn ich weiß,
dass eine Sprache von einem endlichen Automaten akzeptiert wird, dann
weiß ich auch etwas darüber, wie die Struktur der Wörter ist.
Dann weiß ich, die haben alle so eine Pumpstelle, mindestens eine.
Da muss ich aber erstmal wissen, dass das die Sprache eines endlichen
Automaten ist, das ist eine notwendige Bedingung, die hier hinten
steht, notwendige Sache.
Aber es ist nicht hinreichend dafür, dass die vom endlichen Automaten
akzeptiert werden kann.
Es gibt auch Sprachen, die nicht von endlichen Automaten akzeptiert
werden und trotzdem diese Eigenschaft haben.
Also insofern, das reicht so noch nicht.
Das heißt, in der Kontraposition sieht das so aus, hier habe ich
zumindest die Möglichkeit festzustellen, ob eine Sprache nicht von
endlichen Automaten akzeptiert werden kann.
Wenn ich also genau das nachweisen kann, was hier steht, das machen
wir jetzt am Beispiel, das wir uns letztes Mal angeguckt haben, die
Sprache A hoch I, B hoch I oder A hoch M, B hoch N, also beliebig
viele As, auf die genauso viele Bs folgen.
Jetzt machen wir das genauso, wie in dieser Folgerung gerade eben.
Wir nehmen ein beliebiges N aus N her.
Ja, eine beliebige Länge.
Betrachten jetzt ein Wort, ein spezielles Wort, das mindestens N
Zeichen enthält.
Ich spendiere sogar ein bisschen mehr, ich spendiere zwei N Zeichen.
Sage, okay, dann mein Wort ist jetzt hier A hoch N, hier stehen nur As
und da stehen nur Bs.
So, und das sind gerade hier, das sind gerade N und das sind auch N.
Zwei N Zeichen, ein Wort der Länge zwei N.
Ich musste ja nur ein Wort angeben, der Länge mindestens N.
Das ist ein solches Wort, hat sogar Länge zwei N.
Dann muss ich zeigen, egal welche Aufteilung ich wähle mit diesen
Eigenschaften, kann ich bestimmte Dinge zeigen.
Ich betrachte also eine beliebige Aufteilung XYZ des Wortes W, das ich
hier betrachte, das ist mein Wort W.
Jetzt würde ich mir eine beliebige Aufteilung anschauen mit diesen
Eigenschaften.
Also das Wort A hoch N, B hoch N ist dadurch dargestellt.
XY, die Länge von XY ist kleiner gleich N und die Länge von Y größer
gleich 1.
Wenn das Anfangsstück XY maximal N Zeichen enthält, dann heißt das,
mein, wenn ich jetzt hier drüber das male, XY und Z, ich habe das
schon geschickt angeordnet, dass XY liegt irgendwo links von der Mitte
oder maximal genau auf der Mitte.
Das heißt doch, dass das XY irgendein A hoch K ist.
Hier sind genau K Zeichen, kleiner gleich N.
Die Länge von XY ist kleiner gleich N, also kann es nur in dem
vorderen Stück liegen.
Der Betrag von Y ist größer gleich 1, das heißt, dass Y ist irgendein
A hoch J.
Dieses hier, das Y, ist irgendein J, also A hoch J, J Zeichen.
Und das heißt, dass das Z gerade die restlichen Zeichen enthält.
Also die restlichen A's, das sind N minus K A's und N B's hinten dran.
Das heißt, egal welche Aufteilung ich wähle, wenn sie diese beiden
Eigenschaften hat, dann muss das so sein, dass das X eine Potenz von
A's ist, das Y eine Potenz von A's und die beiden zusammengenommen,
beide Potenzen sind kleiner gleich N.
Und jetzt lasse ich das Y einfach raus.
Ich streiche das raus.
Ich muss ja zeigen, es gibt ein I, sodass XY hoch IZ nicht in der
Sprache ist.
Also XY hoch 0Z ist also gerade das XZ, ich nehme also I gleich 0.
Wenn ich das Y rausstreiche, habe ich also J Zeichen rausgestrichen,
das heißt, ich habe hier N minus J A's noch übrig und N B's und das
ist nicht in L von A.
Beziehungsweise es ist nicht in L, das ist hier Quatsch.
Es ist nicht in L.
Das hätte ich rausstreichen müssen, das habe ich jetzt hier damit
gestrichen.
Das ist also nicht in L.
Also dieses Wort XY hoch 0Z ist nicht in der Sprache L.
Und damit habe ich genau das gezeigt, was in der Folgerung stand.
Ich habe ein beliebiges N genommen, habe ein spezielles Wort gesucht,
mit einer beliebigen Zerlegung, mit bestimmten Eigenschaften und
konnte zeigen, dann gibt es eine Potenz, sodass das Wort XY hoch IZ
nicht in L ist.
Und deswegen, nach der Folgerung auf der vorigen Folie, hier steht es
nochmal, dann ist L nicht Sprache eines endlichen Automaten.
Das heißt, auf die Art und Weise können wir jetzt zeigen oder können
wir untersuchen, ob eine Sprache eventuell nicht von einem endlichen
Automaten akzeptiert werden kann.
Die Aussage können wir hinbekommen.
Und wir wissen damit, die Sprache A hoch N oder diese Sprache hier
oben, diese Sprache L kann nicht von einem endlichen Automaten
akzeptiert werden.
Wir hatten das schon vermutet vorher mit diesem Beispiel, wo wir
versucht haben, irgendwie genügend Zustände hinzumalen.
Und jetzt haben wir mit diesem Pumping Lemma und der umgekehrten
Sichtweise darauf, die Möglichkeit, das auch wirklich zu beweisen,
dass man diese Sprache nicht akzeptieren kann.
Und damit sind wir also einen Schritt weiter.
Offensichtlich sind die Sprachen, die wir von endlichen Automaten
akzeptieren lassen können, nicht ausreichend ausdrucksstark, um das zu
formulieren, was wir in Programmiersprachen tatsächlich darstellen
müssen.
Klammerschachtelungen sind dort nicht darstellbar.
Weil wir nicht zählen können.
Das ist das Wesentliche.
Gut, das also dazu.
Folgerung 2.
Es gibt mindestens eine Sprache, zu der kein endlicher Automat A
akzeptiert, sodass L gleich L von A ist.
Das ist die Sprache, die wir gerade angeguckt haben.
Das heißt, es gibt wirklich noch mehr Sprachen als die von endlichen
Automaten.
Hier ist ein anderes Beispiel, mit dem Sie sich selbst beschäftigen
dürfen, wenn Sie sich vorstellen, Sie haben hier nur eine Sprache über
einem Alphabet, das nur aus einem Buchstaben besteht, nur A's.
Und die Wörter unterscheiden sich nur dadurch, dass jedes Wort, das
dort drin ist, hat eine quadratische Länge.
A hoch I Quadrat, I aus N.
Alle Quadratzahlen tauchen als Potenzen dieser A's auf.
Da kann man sich leicht überlegen, dass das dann nicht eine Sprache
sein kann, die von einem endlichen Automaten akzeptiert werden kann.
Können Sie sich leicht überlegen, können Sie das in Übungen machen
oder zu Hause, oder wo immer Sie gerade Lust haben, sich mit diesen
interessanten Fragestellungen zu beschäftigen.
So, das ist, wie gesagt, eine ganz wesentliche Erkenntnis.
Pumping Lemma ist nicht etwas für endliche Automaten mit komischen A's
und B's, das interessiert ja keinen.
Das ist eine grundsätzliche Erkenntnis dafür, wie man mit endlichen
Systemen umgehen kann und wie man dann argumentieren kann, wenn man
Aussagen machen möchte über die Struktur der Prozesse, die von solchen
Maschinen oder Modellen darstellbar sind.
Das gilt für alle solchen endlichen Systeme, deswegen ist das eine
grundlegende Erkenntnis, für die es wert ist, darauf so viel Zeit zu
verwenden, wie ich das jetzt gerade eben gemacht habe.
Jetzt geht es weiter mit einem weiteren Punkt, der für
Wirtschaftsingenieure immer interessant ist, Kostenoptimierung.
Und hier steht jetzt, Äquivalenz und Minimierung endlicher Automaten.
Also wenn ich jetzt in der Lage bin, eine Sprache, also die Sprachen
von endlichen Automaten, sind durchaus nicht uninteressant, aber eben
nicht ausreichend für unsere Programmiersprachen, da kommen wir später
wieder drauf zurück.
Aber jetzt schauen wir uns mal diese endlichen Automaten an.
Und dann kann es natürlich sein, dass es viele verschiedene endliche
Automaten geben kann, die alle die gleiche Sprache akzeptieren.
Und dann würde man auf natürliche Art und Weise sagen, die sind
irgendwie äquivalent.
Und dann interessiert es natürlich darunter zu sagen, was ist
eigentlich dann derjenige, der am kleinsten, der am geringsten Kosten
verursacht.
Also die Fragen sind erstmal, gibt es zu einem Automaten einen
anderen, der dieselbe Sprache akzeptiert und mit weniger Zuständen
auskommt.
Dann ist die Frage, gibt es Automaten, bei denen man zeigen kann, der
hat die minimale Anzahl von Zuständen.
Letzte Frage ist, gibt es eventuell viele verschiedene davon oder sind
die in irgendeiner Form eindeutig.
Und alle diese Fragen sind eben klar zu beantworten.
Man kann zu jedem Automaten einen eindeutigen anderen bestimmen, der
die gleiche Sprache akzeptiert und die minimale Anzahl von Zuständen
hat.
Und minimale Anzahl von Zuständen heißt immer, die Realisierung des
Automaten durch irgendeine technische Einrichtung wie Mikroelektronik
oder ähnliches, der Hardwareaufwand dafür, um diese verschiedenen
Zustände darzustellen, der kann minimiert werden.
Und ich kann genau festlegen, mit einem einfachen Algorithmus, den Sie
gleich kennenlernen werden, wie dieser Automat aussehen muss.
Also das ist das effektive, abbrechende Verfahren zur Bestimmung eines
derartigen Automaten.
Nun müssen wir sehen, wie wir dazu kommen werden, das ist ein sehr
klarer, gut strukturierter Prozess.
Dazu brauchen wir zunächst mal den Begriff der Äquivalenz von
Automaten.
Zwei endliche Automaten, das hatte ich schon angedeutet, mit demselben
Eingabealphabet, die werden immer dann das Äquivalent betrachtet, wenn
sie in Bezug auf ihr Akzeptierungsverhalten nicht zu unterscheiden
sind.
Das heißt, wenn sie die gleiche Sprache akzeptieren.
So, das müssen wir jetzt ein bisschen weiter verfeinern, diese
Aussage.
Es ist klar, dass das eine Äquivalenzrelation ist, ich denke, Sie
wissen alle, was eine Äquivalenzrelation ist.
Das ist also eine Relation auf der Menge der Zustände, S kreuz S
strich, eine Relation auf S kreuz S strich, S die Zustandsmenge eines
Automaten, S strich die eines anderen Automaten.
Und naja, diese Relation, die kann jetzt, wenn ich jetzt sage, S ist
gleich S strich, wenn ich die auf einer Menge betrachte, dann habe ich
die Reflexivität, ansonsten kann ich bei verschiedenen nicht von
Reflexivität reden, aber dann habe ich zumindest die Symmetrie da
drin.
Also, es ist offensichtlich eine Äquivalenzrelation, jetzt sagen wir
mal hier auf S.
Ich betrachte das jetzt mal hier als Relation auf einen und demselben
Automaten und darauf ist es eine Äquivalenzrelation.
Da ist es nämlich so, dass das eine Relation ist, die ist reflexiv,
symmetrisch und transitiv.
Das sind die wesentlichen Eigenschaften einer Äquivalenzrelation.
Kann ich natürlich nur auf einer Menge selbst betrachten, passt nicht
so richtig, wenn ich S kreuz S strich betrachte, dann muss ich schon
sagen, ich habe auf einem Automaten die Relation zwischen zwei
Zuständen eines Automaten.
Beziehungsweise, wenn ich hier, ich gehe nochmal zurück, ich habe
jetzt gerade eben nicht etwas vergaloppiert, tut mir leid.
Ich habe hier die Menge aller Automaten, auf der ist es natürlich,
also ich muss das ganz kurz hier nochmal machen.
Vergessen Sie das hier, was ich gerade eben gemalt habe, das war
Quatsch.
Ich habe ja die Menge der Automaten, die Menge der Automaten kreuz
Menge der, mache ich noch anders, E A kreuz E A, so muss ich es ja
aufschreiben, das betrachte ich ja nur.
E A kreuz E A, das ist die Menge meiner Automaten, die endlichen
Automaten und ich betrachte jetzt Relationen auf diesen Automaten.
Jeder Automat ist zu sich selbst äquivalent, das ist
selbstverständlich, Reflexivität.
Wenn ein Automat A1 äquivalent ist zum Automaten A2, ist A2 auch
äquivalent zum Automaten A1, selbstverständlich symmetrisch.
Und es ist transitiv, wenn A1 äquivalent ist zu A2 oder A2 äquivalent
zu A3, ist natürlich A1 äquivalent zu A3.
Das wissen Sie alles, da habe ich gerade eben einen Schritt zu weit
gedacht und schon auf die nächste Definition einer Äquivalenz auf
Zuständen Bezug genommen.
Da kommen wir aber gleich noch drauf.
Hier geht es ja erstmal nur um die Relation auf Automaten und die ist
hier selbstverständlich reflexiv, symmetrisch, transitiv.
Das also ist sehr einfach.
Dann gibt es einen weiteren Begriff.
Ich möchte meine Automaten möglichst einfach machen.
Und was kann ich dafür alles rauswerfen?
Wenn ich also einen Automaten betrachte, der hier viele verschiedene
Zustände haben kann, irgendwelches schönes Übergangsverhalten mit sehr
vielen Übergängen, dann kann es sein, dass es hier Automaten gibt,
oder Zustände gibt, das ist meinetwegen mein Anfangszustand.
Und es kann Zustände geben, die werden gar nicht vom Anfangszustand
aus erreicht.
Einfachstes Beispiel, ich habe hier einen Automaten, der hat
meinetwegen als Anfangszustand gleich einen Endzustand und hat noch
einen zweiten Zustand, der wird da gar nicht erreicht.
Dann ist der Zustand, der gar nicht erreicht wird, vom Anfangszustand
aus natürlich irrelevant, in Bezug auf das Akzeptierungsverhalten
meines Automaten.
Und mich interessiert ja eigentlich nur, was der Automat alles an
Eigenschaften haben muss, an Komponenten haben muss, damit eine
bestimmte Sprache akzeptiert wird.
Das heißt, etwas, was hier nicht erreicht werden kann, das kann ich
eigentlich auch rausstreichen.
Also, ich kann den Automat vereinfachen, dadurch, dass ich die
Zustände, die nicht erreicht werden können, einfach eliminiere und in
dem Augenblick habe ich einen neuen Automaten, den ich als den zu A
gehörigen vereinfachten Automaten bezeichne.
Und der enthält dann eine eventuell etwas kleinere Zustandsmenge, alle
die, die erreichbar sind vom Anfangszustand aus und die
Übergangsfunktion ist entsprechend eingeschränkt auf F'.
Anfangszustand ist natürlich der gleiche, der ist ja immer erreichbar
und das F' ist jetzt die eingeschränkte Endzustandsmenge, nur
diejenigen, die erreichbar sind.
Das ist sehr naheliegend, das so zu machen und damit haben wir jetzt
schon hier den ersten kleinen Satz, kleine Erkenntnis.
Wenn also A ein Automat ist und A' der zu A gehörige vereinfachte
Automat, dann ist natürlich S0 erreichbar.
S0 ist immer drin, das ist ja klar, weil hier das S0 bei Eingabe des
leeren Wortes natürlich bei S0 bleibt.
Ich muss ja zeigen, es gibt für diesen Zustand, der erreichbar ist,
ein Wort, so dass ich ausgehend vom Anfangszustand auf den Zustand
komme, das ist hier wegen W gleich Lambda der Fall und die Äquivalenz
der beiden Automaten ist eigentlich auch offensichtlich nicht
erreichbare Zustände, während das Akzeptieren eines Wortes nicht
benötigt, deswegen ändert sich das Akzeptierungsverhalten nicht, wenn
ich die rausstreiche, damit bin ich schon fertig.
Und jetzt kommt der Begriff, den ich vorhin etwas vorweggenommen habe,
ich möchte jetzt weitere Zustände charakterisieren, mit denen ich
etwas machen kann, Richtung Reduktion der Anzahl der Zustände.
Und da fangen wir zunächst mal an mit einem Begriff, der sich nennt K
-Äquivalenz, sobald K irgendeine natürliche Zahl ist oder auch die
Null.
Und zwei solche Zustände, also ich habe jetzt hier meine Zustandsmenge
S und meine Zustandsmenge S', das ist also S und S', meine beiden
Automaten.
Es kann auch sein, dass das die gleichen sind, also S gleich S', wenn
ich das auf einem Automaten betrachte, aber wir können ja auch mal
getrennt voneinander betrachten.
Jetzt sage ich, die sind K-Äquivalent, S und S', wenn ich sie in Bezug
auf ihr Verhalten für Wörter bis zur Länge K nicht unterscheiden kann.
Also in Bezug auf das Akzeptierungsverhalten, ausgehend vom Zustand
klein S oder klein S'.
Hier habe ich also einen Zustand, da habe ich einen Zustand.
Das ist hier mein kleines S und das ist ein kleines S'.
Jetzt sage ich, für Wörter der Länge K, maximal der Länge K, kann ich
ihr Akzeptierungsverhalten nicht unterscheiden.
Das heißt, entweder sind beide ein Endzustand, also alle sind die nach
Eingabe von W erreichten Zustände, Delta von SW und Delta' von SW sind
entweder beide Endzustände oder beides keine Endzustände.
Das heißt, dann kann ich sie ja nicht unterscheiden in Bezug auf das
Akzeptierungsverhalten.
Und wenn dieses gilt für alle K, dann nenne ich die beiden Äquivalent,
das heißt, wenn also für beliebige Wörter das Akzeptierungsverhalten,
ausgehend von S und S' in den beiden Automaten A und A', für jetzt
sogar beliebige Wörter nicht unterscheidbar ist, dann nenne ich die
Zustände Äquivalent.
Schauen wir uns ein ganz einfaches Beispiel an.
Welches sind denn die Nulläquivalenten?
Also Nulläquivalent.
Welche wären das denn?
Was soll Äquivalent heißen?
Also, Nulläquivalent, was heißt das denn?
Für alle Wörter kleiner gleich Null ist Delta von SW aus F genau dann,
wenn Delta' von S' W aus F' ist.
Das heißt doch, ich habe doch in meinen Zustandsmengen jeweils, da
habe ich ein F, da habe ich F'.
Das heißt, Zustände aus den beiden Automaten A und A' sind
Nulläquivalent.
Wenn sie entweder beide Nicht-Endzustände sind oder beides Endzustände
sind.
Die sind Nulläquivalent, die kann ich bei Eingabe des leeren Wortes
nicht in Bezug auf das Akzeptierungsverhalten unterscheiden, weil sie
beide Endzustände sind oder beides keine Endzustände.
Sie treffen die gleiche Entscheidung.
Wenn ich ein Zeichen eingebe, 1, Äquivalent, dann bedeutet das, ich
gucke mir an, ein Zustand, noch ein Zustand, jetzt gehe ich einen
Schritt weiter zu einem anderen Zustand.
Auch da ist es so, wenn ich von beiden ausgehend entweder in der
Endzustandsmenge lande oder bei beiden nicht in der Endzustandsmenge,
dann sind sie nicht zu unterscheiden über Eingabe von einem Zeichen.
Wenn aber von einem ausgehend komme ich in, bleibe ich also in der
Nicht -Endzustandsmenge, beim anderen treffe ich auf einen Zustand,
der ist in der Endzustandsmenge, dann würde ich sie bereits
unterscheiden können, bezogen auf das Akzeptierungsverhalten, mit
Eingabe eines Zeichens und so weiter.
Und so werden wir jetzt vorgehen, um zu sehen, also Äquivalenz ist ja
das Problem, da muss ich für beliebige Wörter etwas nachweisen.
Leider sind beliebige Wörter, ziemlich viele vorhanden, weil die
Wörter ja beliebig lang sein können.
Und wenn ich diese Aussage hier zeigen will, zwei Zustände sind
äquivalent, wenn ich das für zwei Zustände nachweisen will, habe ich
eine ziemlich große Aufgabe, für alle Wörter sowas nachzuweisen.
Und die Idee ist, kann ich mich nicht auf Wörter einer gewissen Länge
beschränken, um diese Aussage zu machen.
Und da kommt wieder genau das Gleiche wie beim Pumping-Lemmer, ich
weiß ja, endlicher Automat hat nur endlich viele verschiedene
unterscheidbare Situationen, das trifft hier wieder genauso zu und wir
werden das einschränken können, aber wir müssen uns da ein bisschen
noch Gedanken machen, wie man das formulieren kann.
Also, dass man das auf den gleichen Automaten anwenden kann, ist klar,
dann wären das Zustände ein und desselben Automaten.
Hier nochmal A und A'.
Es kommen zwar ein paar Aussagen, die ich gerade eben schon
vorbereitet habe, wenn zwei Zustände, oder zwei Zustände S und S',
sind also nulläquivalent, wenn sie entweder beide Endzustände sind
oder beide keine Endzustände, das haben wir gerade eben schon gesehen.
Und zwei Zustände sind, also S und S', sind K-äquivalent, genau dann,
wenn, also in beiden Richtungen, für jedes Wort, keiner gleich K, die
Folgezustände, nach Einlesen des Wortes W, nulläquivalent sind.
Das ist die gleiche Aussage, wie beide sind nicht Endzustände oder
beide sind Endzustände.
Das heißt, Delta SW ist in F, genau dann, wenn Delta' von S'W in F'
ist.
Oder eben, die sind beide nulläquivalent.
Und ich kann auch sagen, die beiden Zustände sind beliebig äquivalent,
also S' und S', sind herausgehobene Zustände.
Die beiden Anfangszustände unseres Automaten, S' und S', wenn die
beiden äquivalent sind, dann heißt das, für beliebige Wörter ist das
Akzeptierungsverhalten, ausgehend von S0 oder S0', nicht
unterscheidbar.
Das heißt, wenn ich ein Wort W eingebe in den Automaten A, im
Anfangszustand S0 und ich komme zum Endzustand, dann werde ich auch
bei Eingabe von W in den Automaten A', beginnend mit S0', im
Endzustand landen und umgekehrt.
Und damit ist das also klar, dass die beiden Sprachen identisch sind.
Also wenn S0 äquivalent zu S0' ist, haben die beiden Automaten die
gleiche akzeptierte Sprache, sie sind dann äquivalent.
Und offensichtlich, wenn also jetzt A' gleich A ist, das hatte ich
vorhin schon angedeutet, dann kann ich davon reden, dass ich
Äquivalenzrelationen auf der Menge der Zustände habe.
Das sind sowohl diese Schlange K, also K-Äquivalenz und auch beliebige
Äquivalenz sind jeweils Äquivalenzrelationen, das ist eine sehr
einfache Erkenntnis.
Und von jetzt an werden wir uns also nur noch diese Relationen auf
Zustände eines Automaten betrachten.
Also gehen ein bisschen eingeschränkt, nur noch ein Automat, wir
lassen dieses A' jetzt mal raus und sagen, wir betrachten einen
Automaten und wollen sehen, welche Zustände innerhalb eines Automaten
sind eigentlich äquivalent.
Und die Idee ist natürlich, wenn ich solche äquivalenten Zustände
habe, dann reicht es eigentlich einen zu betrachten, ich muss nicht
alle betrachten, die äquivalent zueinander sind, weil die ja das
gleiche Ein-Ausgabe-Verhalten haben.
Und dann kommen wir zu einer Zerlegung der Zustandsmenge.
Jetzt schauen wir uns mal an, nochmal unsere Zustandsmenge S.
Ich sagte es schon, nulläquivalent sind alle Zustände in der Menge F
und alle Zustände, die nicht in F sind, die sind jeweils
nulläquivalent.
Das heißt, wenn ich mir die Nulläquivalenzrelation anschaue, dann
zerfällt dadurch meine Zustandsmenge in zwei Klassen.
Und das ist diese Partitionierung, die ich betrachte, also hier unten
PK, das ist eine Zerlegung meiner Zustandsmenge gemäß dieser
Äquivalenzrelation.
Sie können bei einer Äquivalenzrelation oder bei einer Menge immer
eine Zerlegung in Klassen machen, in einer Klasse liegen alle die, die
bezogen auf diese Relation äquivalent sind.
Wenn ich also jetzt 1-Äquivalenz betrachte, werde ich hier
irgendwelche Unterscheidungen haben in vielleicht noch hier eine
weitere Klasse, vielleicht da, vielleicht noch, kann es sogar mehrere
geben.
Und wenn ich die 2-Äquivalenz betrachte, werde ich wieder irgendwelche
weiteren Unterteilungen machen.
Und wenn ich die 7-Äquivalenz mache, werde ich noch irgendwelche
weiteren Unterteilungen haben.
Das heißt, ich werde Klassen, die K-Äquivalent sind, für die K-plus-1
-Äquivalent eventuell weiter verfeinern müssen.
Ich betrachte also solche Klassen, das Pi für Partition ist also eine
Zerlegung in Äquivalenzklassen und wir interessieren uns jetzt dafür,
wie können wir diese Äquivalenzklassen insbesondere für das Pi finden,
denn wenn ich die Klassen habe bezüglich der Äquivalenz, dann sind es
eigentlich nur die Klassen, die ich betrachten muss in Bezug auf das
Akzeptierungsverhalten und nicht mehr die einzelnen Zustände.
Weil ja alle Zustände innerhalb einer Klasse das gleiche
Akzeptierungsverhalten haben.
Das wollen wir jetzt machen und dazu müssen wir noch ein bisschen
Überlegungen davor stellen.
Zunächst mal ist es klar, für alle K größer gleich 0 gilt die
Partition bezüglich der Äquivalenz ist feiner, das soll dieses
andeuten, als Pi K, hier ist dargestellt, was das bedeuten soll, die
Klassen bezüglich der Äquivalenz auf der Zustandsmenge sind enthalten
in Klassen bezüglich der K-Äquivalenz für beliebiges K.
Und wenn ich zwei verschiedene solche K-Äquivalenzen betrachte, wobei
das K1 kleiner gleich K2 ist, dann ist die Partitionierung bezüglich
der größeren Zahl, bezüglich K2, eine Verfeinerung der Klassen für die
kleinere Zahl.
Also jede Klasse bezüglich K2, die größer ist als K1, ist enthalten in
einer Klasse für K1.
Das hatte ich gerade eben angedeutet mit dem Bild auf der vorigen
Folie und jetzt kommt hier noch eine Aussage, dann kommen noch eine
Reihe weiterer.
Wenn ich mir jetzt anschaue, zwei Zustände S1 und S2, dann sind die
genau dann K1-Äquivalent,
wenn S1 und S2 Null-Äquivalent sind.
Also K1-Äquivalent heißt ja, für alle Wörter bis zur Länge K1 müssen
die ein nicht unterscheidbares Verhalten haben.
Also insbesondere für das leere Wort sind sie nicht unterscheidbar,
sind also Null-Äquivalent.
Und wenn ich irgendeinen Folgezustand betrachte bei Eingabe eines
Zeichens E, für ein beliebiges Zeichen E, dann müssen diese
Folgezustände K-Äquivalent sein.
Offensichtlich.
Ich schaue mir an, wenn ich ein Zeichen eingegeben habe, dann kann
danach noch irgendein Zeichen oder ein Wort folgen mit maximal K
-Zeichen, mit E zusammen sind es dann maximal K-plus-1-Zeichen, und
sie dürfen dann nicht unterscheidbar sein, das heißt müssen K-plus-1
-Äquivalent sein.
Das ist also hier stets das normale Beweis, das ist wirklich ein so
einfacher Beweis, hier sehr formal ausgeführt.
Genau das, was ich gerade eben gesagt habe, ich weiß ja, wenn die K
-plus -1-Äquivalent sind, dann muss für alle Wörter bis zur Länge K
-plus -1 gelten, dass die erreichten Zustände entweder beide in F sind
oder beide nicht in F, also Null-Äquivalent sind.
Und das heißt aber, dass ich auch betrachten kann, S1 und S2 sind,
also für das leere Wort gilt das natürlich auch, S1 muss also Null
-Äquivalent sein zu S2, und wenn ich also irgendein Zeichen mir
hernehme, dann ist natürlich Delta-S1-EU Null-Äquivalent zu Delta-S2
-EU, das ist das, was man sich auch sofort überlegen kann, dass ich
nach Eingabe, also ausgehend von dem S1, das ist ein Wort der Länge K
-plus -1, die beiden, entweder beide in F-Zustände sind oder nicht,
und dann kann ich natürlich mir das hier genauer angucken, Delta-S1
von E und U, ist Delta-S1-E und darauf das U noch eingelesen, oder
hier Delta-S2-E und dann das U noch eingelesen, das heißt, ich habe
hier genau die Aussage, die ich brauche, die Folgezustände sind dann K
-Äquivalent und das ist das, was hier steht.
Das ist einfach nur eine formale Umformung dieser Aussage, sie ist
eigentlich sehr intuitiv und naheliegend.
Und wir nutzen diese Aussage, diese Erkenntnis jetzt auf eine ganz
einfache Art und Weise, ähnlich wie vorher auch, wir machen wieder,
also hier steht jetzt, hier oben steht A folgt B und hier steht nicht
B folgt nicht A.
Also, hier steht nicht folgt, sondern genau dann wenn in dem Fall,
weil das nicht nur eine Folgerung ist, sondern eine Äquivalenz
-Aussage.
Hier wird genau die Kontraposition hingeschrieben.
Die Negation von dem, was hier oben steht, heißt, hier stand, es ist
S1 Null-Äquivalent zu S2 und für alle E aus E ist Delta-S1-E K
-Äquivalent zu Delta-S2-E und hier unten steht nicht diese Aussage,
also nicht S1 Null-Äquivalent zu S2 oder nicht für alle E aus E, also
es gibt ein E aus E, sodass die Folgezustände von S1 und S2 bei
Eingabe von E nicht K-Äquivalent sind.
Und das ist äquivalent damit, dass S1 nicht K-Äquivalent ist zu S2.
Und dieser Skorola ist die Basis für das Verfahren, das wir anwenden,
um festzustellen, ob zwei Zustände eines Automaten äquivalent sind
oder nicht.
Wir werden zunächst mal anschauen, ob zwei Zustände eventuell nicht
Null -Äquivalent sind und dann werden wir feststellen, ob ausgehend
davon, dass wir schon etwas über gewisse Zustände wissen, die über K
-Äquivalenz, wollen wir schauen, sind eventuell zwei Zustände S1 und
S2 K-Äquivalent, dann nehmen wir uns einfach ein paar von Zuständen
her, S1 und S2, schauen uns an, wohin wir kommen, wenn wir ein Zeichen
E eingeben und schauen, ob diese beiden Zustände hier, ich nenne die
mal S1' und S2', ob die beiden Zustände eventuell nicht K-Äquivalent
sind.
Und wenn diese beiden hier, S1' und S2', nicht K-Äquivalent sind, dann
weiß ich, dann sind die S1 und S2 nicht K plus 1-Äquivalent.
Und auf die Art und Weise kann ich also anfangen, damit, dass ich mir
erstmal angucke, welche Zustände sind nicht Null-Äquivalent, dann
nehme ich irgendein paar her von Zuständen, vor denen ich noch nicht
weiß, ob sie eventuell nicht 1-Äquivalent sind, die sind auch nicht,
die sind also, von denen weiß ich, sie sind durchaus noch Null
-Äquivalent, aber jetzt frage ich mich, sind sie eventuell nicht 1
-Äquivalent.
Da schaue ich mir den Folgezustand an und wenn ich bei Eingabe von E
auf ein paar von Zuständen komme, von denen ich weiß, die sind nicht
Null -Äquivalent, dann waren S1 und S2 nicht 1-Äquivalent.
Und das ist genau das Verfahren, das ich Ihnen gleich im Weiteren sehr
ausführlich darstellen werde.
Ich sehe gerade, dass acht Personen möchten, dass ich langsamer
vorgehe.
Das, was ich gerade eben erklärt habe, ist eigentlich nur eine Vorrede
zu dem, was ich jetzt ausführlich am Beispiel noch vorführen werde und
ich werde Ihnen das Verfahren jetzt hier gleich sehr deutlich
darstellen.
Noch mit einer kleinen Vorerkenntnis, wenn ich mir diese
Partitionierungen anschaue, die wir aus der K-Äquivalenz bekommen, wir
hatten gesagt, das ist eine immer weitere Verfeinerung unserer
Klassen, die wir hier in unserer Zustandsmenge S haben.
Irgendwie werden die alle aufgeteilt.
Sobald wir von der K- zur K-plus-1-Äquivalenz keine Unterscheidung
mehr haben, keine weitere Veränderung haben, werde ich anschließend
auch keine mehr haben.
Das heißt, in dem Augenblick, wenn ich anfange mit Pi-0, dann Pi-1
konstruiere, dann Pi-2, dann Pi-3, also die Partitionierung bezüglich
0, 1, 2, 3, 4-Äquivalenz und ich stelle fest, Pi-3 ist gleich Pi-4
oder eben hier Pi-K ist gleich Pi-K-plus-1, ich habe bei Überlegung
zur Untersuchung jetzt K-plus-1-Äquivalenz eigentlich keine neue
Aufteilung gefunden, dann brauche ich gar nicht weiter zu gucken, dann
bin ich fertig.
Und wenn Sie sich jetzt noch überlegen, also das ist klar, das hatte
ich vorher schon gesagt,
den Beweis sehen Sie gleich, mache ich gleich.
Aber diese weitere Aussage mit diesem Pi-n-1 gleich Pi-n, die kann man
sich auch sehr einfach überlegen.
Nehmen wir mal an, ich hätte von Pi-1 auf Pi-2 auf Pi-3 auf Pi-4 immer
eine Unterscheidung.
Das heißt, ich würde jedes Mal, wenn ich diese K-Äquivalenz um 1
erhöhe von K auf K-plus-1 von 3 auf 4 auf 5 auf 6 übergehe, würde ich
immer mindestens einen neuen Strich einführen, das heißt, ich würde
ein Element rausnehmen aus einer Klasse, weil das auf einmal in eine
eigene Klasse gehört.
Wie oft kann ich denn bei einer Menge von N-Elementen Elemente
abspalten und die in eigene Klassen stecken?
Ich habe mir N-Elemente zur Verfügung, wie oft geht das denn?
Jedes Mal was Neues, das geht ja nur N-1 Mal, ich kann nur N-1 Mal ein
Element rausholen, danach habe ich Klassen, die haben alle nur ein
Element und ich bin fertig.
Das heißt, spätestens für K gleich N-1 bin ich fertig mit dieser
Partitionierung.
Und das heißt, ich habe ein endliches Verfahren, um die Äquivalenz zu
überprüfen.
Ich brauche nur endlich solche K-Äquivalenzen anzuschauen und werde
dann wissen, welche Zustände äquivalent sind.
Und das habe ich nicht dadurch gemacht, dass ich für zwei Zustände
untersucht habe, ob sie für alle Wörter das gleiche Verhalten haben,
sondern ich habe das dadurch gemacht, dass ich für alle Paare
untersucht habe, gibt es zwei Wörter irgendeiner Länge, die zu einem
unterscheidbaren Verhalten führen für diese zwei Zustände.
War das also dadurch, dass ich etwas aussage über Nicht-Äquivalenz?
Ja, das muss ich ja nur zeigen, es gibt ein Wort, für das diese
Zustände ein unterschiedliches Verhalten zeigen.
Und das ist jetzt die gleiche Überlegung wie beim Pumping-Lemmer, da
ja lange Prozesse oder bei endlichen Automaten die Prozesse nicht
beliebig lang sein können, die ich betrachten muss, weil ich immer was
rausschneiden kann, weiß ich, ich brauche nur ein endliches
Anfangsstück zu betrachten, ich brauche nur Wörter bis zur Länge N.
Damit habe ich das Verhalten der Automaten vollständig analysiert.
Für längere Wörter kann eigentlich nichts Neues mehr passieren, das
ist etwas, was sich nur wiederholt von Sachen, die ich vorher schon
gemacht habe.
Also, hier steht der Beweis für die Aussage A, formal als
Induktionsbeweis aufgeschrieben, also zwei Zustände sind
charaktervalent, genau dann, wenn, das haben wir vorher überlegt, die
Folgezustände bei Eingabe von Wörtern mit Länge maximal K null
-äquivalent sind und dann kommt die Behauptung, wenn also Pi K gleich
Pi K plus 1 ist, das ist diese Aussage hier, dann sage ich, dass für
alle J größer gleich K, dann Pi J gleich Pi J plus 1 ist.
Das ist das im Prinzip, was hier steht, das wird Punkt, Punkt, Punkt.
Punkt, Punkt, Punkt ist keine formale Aussage, das ist die formale
Aussage dazu.
Das mache ich durch Induktion, für J gleich K, das ist also das Erste,
wo ich etwas zeigen muss.
Das gilt nach Voraussetzung, das weiß ich, für J gleich K steht es
bereits dort, das ist die Induktionsvoraussetzung in dem Fall, für J
gleich K ist diese Aussage wahr.
Und jetzt kommt der Schluss von J auf J plus 1, das heißt, ich
betrachte zwei Zustände, die J plus 1 äquivalent sind, beziehungsweise
die Partitionierung Pi K plus 1 oder Pi J plus 1.
Und wenn die Pi J plus 1 äquivalent sind, dann heißt das, ich habe für
alle Wörter bis zur Länge J plus 1 die Nulläquivalenz der erreichten
Zustände.
Und wenn das für alle Wörter der Länge maximal J plus 1 gilt, dann
gilt es natürlich auch darüber, dass ich sage, für alle E aus E und
für alle W aus E-Stern mit W kleiner gleich J, da teile ich eben die
Wörter der Länge J plus bis zur Länge J plus 1 einfach auf, in
Anfangszeichen plus irgendein Rest.
Und ich muss auch noch das leere Wort betrachten, das ist die gleiche
Aussage, ist S also Nulläquivalent zu S' und Delta S E W ist
Nulläquivalent zu Delta S' E W.
Also für das leere Wort äquivalent und für alle anderen natürlich auch
dann Nulläquivalent, die Vorbildzustände.
Und wenn ich diese Aussage habe, dann weiß ich natürlich, dass dann
Delta S E, das Delta S E ist dann J-Äquivalent zu Delta S' E, jetzt
weiß ich aufgrund dieser Voraussetzung, es ist für J gilt das bereits,
es ist also Pi J gleich Pi J plus 1, deswegen ist diese Äquivalent
gleich der Äquivalent.
Und wenn das so ist, dann steht hier für das leere Wort, sind S und S'
äquivalent, S Nulläquivalent S' und für die Zustände Delta S E und
Delta S' E gilt die J plus 1 Äquivalent, dann gilt insgesamt natürlich
gerade die J plus 2 Äquivalenz für S und S'.
Ja, weil ich dann ein Wort, das mit E beginnt, kann ich irgendwas der
Länge J plus 1 anschließen, dann habe ich die J plus 2 Äquivalenz.
Hier gibt es eine kurze Frage.
Wie hat man sich eine Partition vorzustellen?
Ups, so, das ist eine Partition.
Also ich habe eine Zustandsmenge, jetzt nehme ich schon einige
Zustände raus, das ist die einfachste Partition, S und das hier ist S
minus F.
Und dann mache ich also eine Partition, das ist also eine Aufteilung
einer Menge in das junge Detailmengen.
Das sind das junge Detailmengen, also S ist gleich Vereinigung, B, I,
I gleich 1 bis K, jedes B, I ist enthalten in S und für alle I, J ist
B, I geschnitten, B, J gleich leer.
So ist es formal, Partition.
Also eine disjunkte Aufteilung einer Menge in Teilmengen,
Standardbegriff.
Das habe ich, glaube ich, hier nicht genau.
Habe ich beantwortet, damit ist das klar.
Jetzt kommt schon die nächste Frage.
Für was genau steht Pi?
Pi steht für die Menge, also, ups, muss ich nochmal, ich muss dran
denken, dass ich hier immer gleich auf den Ansatz sage.
Also das Pi ist einfach eine Menge von Mengen.
In dem Fall wäre also das Pi, könnte ich hier sagen, das wäre in dem
Fall die Menge B1 bis BK, in diesem Beispiel.
Das wäre nur ein abstraktes Beispiel.
Das Pi ist eine Partition, besteht aus einer Menge von Blöcken, und
diese Blöcke sind jeweils Äquivalenzklassen, in dem Fall, das ist eine
formale Definition, die hier steht, in diesem Teil, und wir hatten
vorher auf der Folie stehen gehabt, dass wir eine Partitionierung,
dass das Pi eine Menge von Äquivalenzklassen ist, jeweils die Menge
der Zustände, die äquivalent sind zu einem gewissen Zustand S.
So ist es einfach dargestellt.
Das ist eine klassische Partitionierung.
So, das also zu diesem vorbereitenden Aussagen.
Jetzt die Frage, wie mache ich das Verfahren?
Wie reduziert man einen Automaten?
Zunächst mal entferne ich alle nicht erreichbaren Zustände,
offensichtlich.
Was ich nicht erreichen kann, schmeiße ich weg.
Ich habe also einen einfachen Automaten oder einen vereinfachten
Automaten anschließend.
Und dann möchte ich die Klassen äquivalenter Zustände bestimmen, also
die entsprechende Partitionierung, Aufteilung meiner Menge in eine
Reihe von Untermengen, disjunkte Aufteilung in Teilmengen.
Das sind meine äquivalenten Zustände.
Alle Zustände innerhalb einer solchen Klasse sind äquivalent.
Und dann sage ich, da die äquivalent sind, reicht es einen von denen
zu betrachten, weil die ja alle untereinander das gleiche Verhalten
haben.
Deswegen sage ich einfach, ich nehme jetzt einen Repräsentanten für
meinen Zustand S, um diese Klasse darzustellen.
Und ich habe jetzt im Prinzip einen Automaten, der auf den
Repräsentanten der Äquivalenzklassen arbeitet.
Und das ist ein etwas vereinfachter Automat.
Das sehen wir gleich an einem Beispiel.
Jetzt ist die Frage, wie mache ich hier diesen Schritt 2.
Schritt 3 ist dann relativ einfach.
Schritt 2 ist das interessante Verfahren.
Der Automat, der dabei rauskommt, ist dann der, bei dem alle Zustände
paarweise nicht äquivalent zueinander sind.
Ich kann also nichts mehr einfacher machen.
Und der außerdem vereinfacht ist, also er hat keine nicht erreichbaren
Zustände.
Das ist ein reduzierter Automat.
Und wir werden sehen, dass der in endlicher Zeit konstruierbar ist und
dass er eindeutig bestimmt ist.
Und das ist jetzt der Algorithmus, der hier in Programmiersprachenform
dargestellt ist.
Was wird hier dargestellt?
Wir gehen genau so vor, wie ich das angedeutet habe.
Ich markiere für aufsteigendes K alle Paare von Zuständen, die nicht K
-äquivalent sind.
Aufsteigendes K, ich fange also mit K gleich 0 an.
Ich möchte Paare von Zuständen markieren.
Paare von Zuständen, also mache ich mir eine Tabelle.
Und wenn ich hier irgendeinen Zustand S habe und irgendeinen Zustand
S', dann werde ich in der Tabelle in diesem Feld markieren, ob diese
beiden Zustände äquivalent sind oder nicht.
Wenn ich also hier ein Kreuzchen mache, dann heißt das, die sind nicht
äquivalent.
Und ich fange damit an, dass ich zunächst mal die Nulläquivalenz
betrachte.
Also dann heißt das doch sofort, wenn zwei Zustände S und S' nicht
beide Endzustände sind, dann sind sie nicht Nulläquivalent, dann werde
ich die markieren.
Also wenn S aus F ist und S' nicht aus F oder umgekehrt, dann markiere
ich dieses Feld.
So, und jetzt geht das genauso weiter.
Ich möchte jetzt ganz im Sinne dieses einen Lemmas, das wir uns
überlegt haben, also feststellen, ob zwei Zustände nicht K plus 1
äquivalent sind, indem ich überprüfe, ob ich von diesen beiden
Zuständen durch Eingabe irgendeines Zeichens auf ein paar von
Zuständen gelangen kann, die bereits markiert sind, also von denen ich
weiß, sie sind nicht äquivalent, nicht K-äquivalent.
Ich nehme mir also irgendein, so hier irgendwelche zwei Zustände her,
sagen wir mal hier jetzt S1 und S2, da steht wieder S' und S', kann
auch S1 und S2 sagen.
Jetzt schaue ich mir an, wenn ich von S1 und S2 aus mit irgendeinem
Zeichen, das ist das, was hier steht, SS', ich gehe mit irgendeinem
Zeichen E weiter und komme dabei auf, also von S1 meinetwegen auf S
und von S2 auf S', das mit E, da mit E und das ist bereits markiert,
dann weiß ich, die Folgezustände von meinen S1 und S2, von denen weiß
ich, sie sind nicht äquivalent, also können diese beiden auch nicht
äquivalent sein.
Ich habe einen Fall gefunden, dass die sich mit ihrem
Akzeptierungsverhalten unterscheiden.
Deswegen markiere ich die dann auch.
Und das ist das ganze Verfahren.
Und da das Ganze symmetrisch ist, und da natürlich ein Zustand mit
sich selbst äquivalent ist, brauche ich nur die untere Dreiecksmatrix
zu betrachten.
Und das ist das, was wir auf der nächsten Folie machen, hier steht
nochmal ein schöner Satz, und gleich kommt der Beispiel, also wenn der
Algorithmus ausgeführt wird, wenn am Ende ein Paar von Zuständen nicht
markiert ist, und wir haben keine Veränderung mehr festgestellt, dann
müssen die beiden äquivalent sein, weil wir keinen Fall entdeckt haben
unter den Wörtern bis zur Länge n-1, sodass die sich unterscheiden in
ihrem Akzeptierungsverhalten, und dann weiß ich, auch für beliebig
lange Wörter können die sich nicht mehr unterscheiden.
Hier ist ein einfacher Automat, können Sie sich kurz anschauen, der
hat hier vorne so eine komische Schleife mit 0 und 1, und mit 1 kann
ich von 0 auf S2 gehen, mit 0 oder 1 wieder zurück, dann kann ich mit
0 auf S1 gehen und dann kann ich mit 0 auf S4, mit 1 auf S5 gehen,
beides Endzustände, und von S4 komme ich wieder 0 auf 1, S3, mit 1
wieder auf S4 zurück, und hier unten zwischen S5 und S3 kann ich schön
hin und her wandern.
Das ist das Diagramm und die Tafel, und auf der nächsten Folie sehen
Sie nochmal die Tafel und das Bild dieser unteren Dreiecksmatrix, die
wir jetzt ausfüllen wollen.
Jetzt mache ich das Verfahren eben ganz langsam.
Der erste Schritt war, ich markiere alle Paare von Zuständen, von
denen einer ein Endzustand ist und der andere nicht.
Die markiere ich mit X0 und das X0 heißt nicht nulläquivalent.
Hier unten sehen Sie, S4 und S5 sind Endzustände, die sind hier
eingekringelt, das soll andeuten, das sind Endzustände.
Ich muss also nur betrachten Paare von Zuständen S4 mit irgendeinem
anderen und S5 mit irgendeinem anderen, und es ist klar, dann sind
diese alle sofort auszufüllen mit X0, die sind alle nicht
nulläquivalent.
Sie sehen, da fallen schon mal ganz viele Felder hier weg.
Und jetzt geht es weiter, ich weiß, die sind nicht nulläquivalent.
Jetzt geht es weiter, ich muss jetzt die betrachten, die noch nicht
markiert sind, also von denen ich noch nicht weiß, ob sie eventuell
nicht äquivalent sind.
Für jedes Paar, die noch nicht markiert sind, schaue ich mir an, ob
ich irgendein Eingabezeichen habe, sodass ich auf ein Zustandspaar
komme, das bereits markiert ist.
Also diejenigen Paare, die durch Eingabesymbole 0 oder 1, das sind
meine beiden Eingaben, die ich habe, auf ein bereits markiertes
Zustandspaar führen, markiere ich mit X1.
Schauen wir uns das erste Feld hier an, S1, S0.
S1, S0, das sind diese beiden Zustände, S0 und S1.
Wenn ich eine 0 eingebe, komme ich auf S1 und S4.
S1 und S4, dieses Feld, S1, S4, S1, dieses Feld hier, das ist
markiert.
Also muss ich hier oben ein Kreuz X1 machen.
Genauso für die anderen Paare, und Sie stellen fest, die hier grün
angegebenen Paare für den zweiten Schritt, das sind alles Paare von
Zuständen, also S2, S1, oder S1, S2, S2, S3, S0, S3, von denen aus
komme ich auf Paare von Zuständen, die bereits markiert sind.
Von den anderen, also S2, S0, S1, S3 und S4, S5, habe ich noch keine
solche Möglichkeit gefunden, auf ein Paar zu kommen, das bereits
markiert ist.
Also wenn ich da ein 0 oder ein 1 eingebe, komme ich auf ein nicht
markiertes Feld.
Dritter Schritt, ich mache das weiter und stelle fest in dem Fall,
dass hier oben S2, S0, wenn ich von S2, S0 ausgehe, S2, S0, hier die
beiden, mit einer 0 komme ich auf S1 und S0, S1, S0 ist bereits mit X1
markiert, also ist nicht äquivalent, deswegen sind S2, S0 ebenfalls
nicht äquivalent, in dem Fall nicht 2-äquivalent.
Sie waren noch 0-äquivalent und waren noch 1-äquivalent, aber sie sind
nicht 2-äquivalent.
Die anderen beiden Felder bleiben bestehen, können sich überzeugen und
ich stelle fest, ich habe, wenn ich jetzt die 3-Äquivalenz anschaue,
keine weiteren Einträge.
Wenn sich von 2-Äquivalenz auf 3-Äquivalenz keine Änderungen ergeben,
weiß ich, ich bin fertig.
Ich muss ja gar nicht mehr weitermachen.
Das sind die Paare von Zuständen, die jeweils äquivalent sind.
Damit bin ich also fertig, ich habe hier herausgefunden, S1 und S3
sind äquivalent und S4 und S5 sind äquivalent.
Das, was wir hier machen, ist übrigens eine Technik, die Sie an
anderer Stelle auch kennen, man nennt das auch dynamisches
Programmieren.
Wir haben mit einfachen Fällen angefangen, Wörter der Länge 0, haben
für die Erkenntnisse gesammelt, die X0 eingetragen, haben Wörter einer
weiteren Länge betrachtet und können aus dem, was wir für die Wörter
der Länge 0 betrachtet haben, auf die Wörter der Länge 1 schließen.
Für das, was wir für Wörter der Länge K betrachtet haben, können wir
auf Wörter der Länge K plus 1 schließen.
Und so weiter.
Das ist das typische Vorgehen des dynamischen Programmierens.
Das ist immer so ein Ausfüllen von irgendwelchen Tafeln, das hat man
so genannt.
Sie werden das dynamische Programmieren auch im Bereich des Research
an verschiedensten Stellen kennenlernen.
Oder haben Sie vielleicht schon kennengelernt.
Das ist das Verfahren für die Feststellung, ob zwei Zustände
äquivalent sind oder nicht.
Hier haben wir alle festgestellt, die nicht 0, nicht 1, nicht 2
äquivalent sind, und die anderen sind schon äquivalent, weil sich von
nicht 2 keine weiteren nicht 3 Äquivalenten ergeben haben.
Also alle, die 0, 1 und 2 äquivalent sind, sind auch 3, 4, 5, 6
äquivalent.
Und jetzt kommt die Reduktion.
Wir nehmen uns jetzt die Konstruktion eines neuen Automaten vor.
Dieser neue Automat habe Zustände, die gerade diese Äquivalenzklassen
sind.
Und der Anfangszustand ist die Klasse des Anfangszustandes, und die
Einzustandsmenge ist die Menge aller Klassen, die Endzustände
enthalten.
Und die Übergangsfunktion ist jetzt eine Übergangsfunktion auf
Klassen.
Es ist also der Übergang, ausgehend von einer Klasse von S, bei
Eingabe von E komme ich auf die Klasse des Zustands, den ich bei
Eingabe von E im Zustand S erreiche.
Das heißt, ich kann den Folgezustand, diese Klasse, hier die
Folgeklasse, dadurch definieren, dass ich irgendeinen Repräsentanten
herausnehme und dessen Folgezustand betrachte, und dann ansehe, was
ist dessen Klasse.
Das heißt, ich kann über den Repräsentanten diese Übergangsfunktion
definieren, hier muss ich eigentlich zeigen, dass dies auch wohl
definiert ist, das heißt, es ist unabhängig davon, welchen Zustand ich
herausnehme, das ist eine relativ einfache Überlegung.
Aber diese Frage, ist das Ganze wohl definiert, das ist etwas, was man
sich noch überlegen muss, was aber sofort einsichtig ist.
Wenn ich irgendwelche zwei Zustände habe, die in einer Klasse drin
liegen, S und S', die äquivalent sind, dann sind die Folgezustände
natürlich auch äquivalent, kann man sich sehr schnell überlegen, ist
aber eigentlich eine extra Aussage.
Na, was habe ich jetzt hier gemacht?
Ist mir das Ding hier verrutscht.
Was ist denn hier jetzt mit dem, der mag mich nicht?
Warum bleibt S3, S1 leer?
Ich dachte, ich hätte es beantwortet.
S3, S1, gehen wir zurück auf Folie 40.
S3, S1, schauen wir uns das an.
S3, S1, dieser Zustand und dieser Zustand.
Wenn ich von S1, S3 mit 0 weitergehe, komme ich auf S4 und S5.
S4 und S5 sind beides Endzustände.
Wenn ich mit 1 weitergehe, komme ich auf S5, S4.
Natürlich wieder beides Endzustände.
Das heißt, ich kann S1 und S3 nicht unterscheiden, wenn ich mir
anschaue, jede Möglichkeit, über Eingabe eines Zeichens auf
Folgezustände zu kommen.
Das Akzeptierungsverhalten ist gleich.
Beides Endzustände.
Wenn ich mir das andere Paar anschaue, S5, S4, haben wir hier.
S5, S4, diese beiden.
Wenn ich den 0 eingebe, komme ich von beiden aus auf S3.
S3 ist natürlich, ist hier in diesem Fall nicht ein Endzustand.
Mit 1 komme ich auf S5, das ist ein Endzustand.
Für beide Eingaben, 0 und 1, kann ich das Akzeptierungsverhalten der
Folgezustände nicht unterscheiden.
Das heißt, ich kann sie nicht ausfüllen.
Man kann die beiden Felder nicht markieren.
Und mehr brauche ich nicht zu machen.
Damit sind wir also hier auf diesem Fall.
Und jetzt machen wir das am Beispiel.
Wir wollen also jetzt den reduzierten Automaten konstruieren, der
jetzt vorher also diese sechs Zustände, S0 bis S5, hatte.
Und jetzt müssen wir das Ganze neu definieren.
Das ist unsere Zustandstafel des alten Automaten.
Das ist unsere Tabelle, die wir gebaut haben.
Und wir wissen, dass jetzt S1 und S3 äquivalent sind, S4 und S5.
Das heißt, wir müssen den Automaten A', den reduzierten, so bauen,
dass wir diese hier als unsere Klassen betrachten.
Klasse von S0, S1, S2, S4.
Das sind unsere Äquivalenzklassen.
S1 und S3 sind hier äquivalent und S4 und S5.
Dafür schreiben wir einfach S0', S1', S2' und S4'.
Das sind unsere vier Zustände, die übrig geblieben sind.
Und die Endzustandsmenge, da S4 und S5 äquivalent sind, ist das jetzt
also hier genau diese Klasse von S4 oder Klasse von S5, das ist völlig
egal.
Das ist also jetzt unsere Endzustandsmenge.
Und das heißt, wenn wir die Tafel aufbauen, dann sieht die jetzt etwas
kleiner aus.
Wir gehen jetzt von der Klasse von S0 über auf die Klasse von S1 bzw.
die Klasse von S2.
Das stand ja hier oben auch, das ist einfach nur die einfache
Übertragung.
S1 und S2.
Und entsprechend sind die anderen Felder hier auch auszufüllen.
Das ist einfach die Übertragung der alten Übergangsfunktion auf die
neue Zustandsmenge und die sieht halt einfach kleiner aus, weil wir
die Äquivalenten hier zusammenfassen konnten.
Und wenn wir das jetzt betrachten in Bezug auf die grafische
Darstellung, war das unser alter Automat.
Der hatte hier diese Schleife da oben und dann hier, das ist ein
bisschen anders dargestellt aus Platzgründen.
Und jetzt werden die beiden Endzustände zusammengefasst und die S1 und
S3 werden zusammengefasst und dann kommt der Automat raus, der hier
steht, deutlich einfacher und er hat genau das gleiche
Akzeptierungsverhalten.
Und das ist ein einfach ausführenbares Verfahren.
Sie füllen diese Tabelle aus und das geht relativ schnell, dann wissen
Sie, welche Zustände äquivalent sind, dann können Sie diesen Automaten
sofort reduzieren, in der hier dargestellten Art und Weise.
Fazit ist also, dass wir zu jedem endlichen Automaten einen
äquivalenten, minimalen endlichen Automaten konstruieren können.
Es gibt immer einen.
Dieser Automat ist der sogenannte Äquivalenzklassenautomat, weil die
Zustände, die die Äquivalenzklassen sind, man nennt ihn manchmal auch
Faktorautomat, schreibt das dann als A nach Pi oder auch A nach
Schlange, nach der Partitionierung, die wir bezüglich der Äquivalenz
haben.
Und das Wesentliche ist halt, wie wir diese Äquivalenz bestimmen.
Der ist dann bis auf Isomorphie eindeutig bestimmt und lässt sich halt
in endlicher Zeit konstruieren.
Und damit sind wir mit der Äquivalenzbetrachtung schon fertig und mit
der Reduktion.
Wir wissen jetzt, wie wir die Automaten vereinfachen können.
Okay, so können wir das jetzt sehr deutlich vereinfachen, was wir
betrachten.
Jetzt kommt schon der nächste Aspekt.
Manchmal sehen die Automaten ziemlich kompliziert aus und eigentlich
wollen wir die gar nicht so kompliziert machen.
Wobei das, was ich jetzt hier beschreibe, zunächst aussieht wie eine
noch größere Komplexität, wenn wir von Nichtdeterminismus reden.
Nichtdeterministische endliche Automaten, was kann das sein?
Das ist ein Automat, wie gesagt, der sieht zunächst mal noch
aufwendiger aus, als der deterministische endliche Automat.
Bei dem ist nämlich die Übergangsfunktion nicht einfach nur ein
Übergang von Zustand und Eingabe auf Folgezustand, sondern wir haben
hier irgendeine Menge von Folgezuständen.
Das heißt im Prinzip, wir haben eine Unsicherheit über den
Folgezustand.
Es kann irgendeiner sein aus der Menge, derjenigen angegeben sind.
Der Folgezustand ist nicht eindeutig.
Die Menge der Folgezustände kann leer sein, irgendeine Teilmenge von
S.
Und das Schöne ist, wir können auf die Art und Weise Automaten
bezüglich ihres Akzeptierungsverhaltens wesentlich intuitiver
darstellen, wesentlich einfacher.
Also hier ist ein typisches Beispiel.
Wir wollen einen Automaten konstruieren, bei dem Folgendes passiert.
Schauen Sie sich den mal an.
Welche Sprache wird von dem Automaten akzeptiert?
Sie sehen, hier haben wir Mengen.
Hier stehen überall Mengen drin von Zuständen, wobei auch wenn der
Übergang eindeutig ist, ist das auch eine Menge, die nur ein Element
enthält.
Und hier haben wir sogar gar keinen Übergang mehr.
In der grafischen Darstellung als Zustandsdiagramm sieht er wesentlich
einfacher aus.
Man sieht das sofort.
In S0, in dem Anfangszustand, dürfen wir beliebig A oder B eingeben.
Das ist hier dargestellt.
Wir können in S0 bleiben.
Wir können aber auch mit A in den Zustand S1 übergehen.
Und da können wir beliebig A's und B's eingeben und bleiben in S1.
Wir könnten aber auch mit einem A auf S3 übergehen, aber dann geht es
nicht weiter.
Und das gleiche können wir für B's machen.
Wir könnten von S0 mit B in S2 übergehen, könnten dort beliebig lange
A's und B's eingeben und wenn wir dann am Ende ein B haben und nach S3
gehen, geht es nicht weiter, aber das Wort ist akzeptiert.
Das heißt, welche Wörter werden akzeptiert?
Wörter, die auf ein Zeichen enden, A oder B, das vorher schon einmal
aufgetaucht ist.
Wenn ich also ein Wort habe, das mit A endet, dann muss das A vorher
schon mal aufgetaucht sein.
Wenn das Wort mit B endet, muss das Zeichen B schon mal vorher
aufgetaucht sein.
Das ist damit ausgedrückt.
Und das steht hier unten nochmal drunter.
Also das letzte Zeichen muss vorher schon mal aufgetaucht sein und X
ist A oder B.
Das ist mit diesem einfachen Automaten dargestellt.
Sie sehen hier, das ist klar, Sie haben hier für ein Zeichen A
verschiedene Übergänge dargestellt.
Das heißt, wir haben hier gewisse Unsicherheiten drin oder
verschiedene Möglichkeiten drin, die man gehen könnte und damit haben
wir ein Akzeptierungsverhalten, das hier steht, direkt übersetzt in
die Definition eines Automaten.
Und jetzt muss man natürlich überlegen, was heißt das eigentlich für
die Fortsetzung der Übergangsfunktion auf Wörter?
Wenn ich mit einem Zeichen aus S auf eine Folgezustandsmenge übergehe,
was heißt das denn, wenn dahinter noch ein Wort folgt?
Naja, dann muss ich mir irgendeinen Zustand aus der Folgezustandsmenge
hernehmen, S', und sehen, wie komme ich von dem aus weiter, was ist
die Folgezustandsmenge ausgehend von diesem Zustand, S', bei Eingabe
des Wortes W, bzw.
ich muss mir natürlich nicht nur einen hernehmen, sondern jeden, in
den ich gehen könnte.
Das heißt, mein Delta-Stern, also ausgehend von S, bei Eingabe eines
Zeichens E und irgendwelcher weiteren Zeichen, ist das Delta-Stern von
Delta SE, W, und das Delta SE ist eine Menge von Zuständen.
Das heißt, das ist die Vereinigung aller Delta-Stern von S' W, wobei
S' aus Delta von SE ist.
Das ist hier dargestellt, ich muss alle solche, wenn ich also
irgendeinen S' da drin habe, muss ich natürlich hier auch sehen, was
ist da für eine Folgezustandsmenge, wenn ich hier irgendeinen S' habe,
muss ich sehen, was ist dort die Folgezustandsmenge, die können sich
beliebig überlappen, ich muss also die Vereinigung aller dieser Mengen
bilden, das ist eine natürliche Fortsetzung, hier etwas aufwendiger
als bei der Fortsetzung eines deterministischen Automaten.
Also, wenn wir hier diesen einfachen Automaten nochmal anschauen, das
Beispiel von vorher, und wir betrachten jetzt ausgehend von S'0 das
Verhalten für Eingabe A, B, wenn wir ausgehend von S'0 A eingeben,
kommen wir auf die Menge S'0, S'1, wie hier dargestellt, und wenn wir
von S'0 ausgehen, wieder mit B, kommen wir auf S'0, S'2, und wenn wir
von S'1 ausgehen, mit B, dann kommen wir mit S'1 und B kommen wir auf
S '1, das heißt wir haben dann S'0, S'2, das ist diese Menge,
vereinigt mit der Menge S'1, das heißt S'0, S'1, S'2 ist dann die
Folgezustandsmenge bei Eingabe von A und B.
Und so geht es dann weiter.
Und dann kann man sich genauso überlegen, wie ich jetzt die
Konfigurationen, das Verhalten von nicht deterministischen endlichen
Automaten definiere, genau wie vorher.
Ich muss mir anschauen, ein Zustand und das Restwort, was noch auf dem
Eingabeband steht, das ist mein Restwort hier vorn, das habe ich schon
bearbeitet, das, was hier hinten steht, von da bis da, das ist mein
Wie, und dann weiß ich, wie ich weiter vorgehen muss, und wenn ich
jetzt irgendeine Konfiguration habe, deswegen fange ich an mit S'0 und
W, das ist meine Anfangskonfiguration, dann habe ich jetzt auf einmal
mehrere Möglichkeiten, auf irgendein S zu gehen, wenn das hier ein S
'0EW ist, würde ich hier auf SW kommen, hier vielleicht auf S' und W,
und hier auf S'2W, je nachdem, wenn also S', S'2' in der Menge der
Folgezustände von S'0 und E drin sind, also von S'0 und der Eingabe
von E, dann habe ich diese Verzweigung, das heißt, ich habe hier auf
einmal nicht mehr nur eine lineare Folge von Konfigurationen, sondern
ein Baum von Konfigurationen, weil ich aus jeder Konfiguration
eventuell mehrere Folgezustände erreichen kann.
Für jeden Zustand aus der Folgezustandsmenge von S und der Eingabe von
E, habe ich hier natürlich eine neue Konfiguration hinzuschreiben, und
entsprechend habe ich einen Baum von solchen Konfigurationsfolgen, und
da kann man das Ganze genauso gut reflexiv-transitiv betrachten, und
über diese Definition werden wir dann beim nächsten Mal darauf kommen,
was dann die Sprache ist, die von so einem nicht deterministischen
endlichen Automaten akzeptiert wird.
So, Sie haben heute viele interessante Dinge noch einmal
kennengelernt, insbesondere die fundamentale Erkenntnis, dass bei
endlichen Systemen es ausreicht, wenn ich deren Verhalten beschreiben
will, mir Anfangsstücke endlicher Länge anzugucken.
Wenn ich die analysiert habe, weiß ich etwas für beliebig lange
Prozesse.
Diese Erkenntnis ist ganz wichtig, deswegen war es wert, darauf ein
bisschen mehr Zeit zu verbringen, als ich das sonst normalerweise
machen würde.
Vielen Dank für die Aufmerksamkeit.