Also hier ist jetzt dieser Automat ohne Ausgabe.
Der hat interne Zustände, hat den Lesekopf.
Das Eingabeband kann von links nach rechts bewegt werden.
Wir lesen also dadurch die verschiedenen Zeichen, die hier drauf
stehen.
Das Band wandert an dem Kopf vorbei und irgendwann haben wir alles
gelesen und dann können wir also feststellen, ist der Zustand, in den
wir dann gekommen sind, ein Endzustand, also in der Menge F aller
Endzustände oder ist das ein anderer Zustand, dann können wir sagen,
das Wort wird akzeptiert oder nicht.
Wir haben also jetzt wieder eine Vereinfachung des Automaten.
Jetzt haben wir überhaupt keine Ausgabefunktion mehr, nur eine
Übergangsfunktion, aber wir haben eine Quasi-Ausgabe, die für einen
Zustand sagen kann, ist das ein akzeptierender oder ein nicht
akzeptierender Zustand.
Das sind die beiden Möglichkeiten.
Und an solchen Automaten nennen wir Akzeptor, weil er uns etwas sagt
darüber, ob wir ein Wort als Element einer Sprache akzeptieren wollen
oder nicht.
Arbeitsweise ist so wie vorher auch, hier vorne, der Automat muss zu
Anfang erst mal richtig initialisiert werden.
Dann nehmen wir immer an, dass das schon erfolgt.
Also er ist über dem linkesten Zeichen des Eingabewortes und im
Anfangszustand S0 und dann liest er so lange immer wieder ein Zeichen
auf dem Band, bis er alle Zeichen gelesen hat, bis also kein Zeichen
mehr da ist.
Geht immer in einen Folgezustand über und am Ende schauen wir uns an,
in was für einem Zustand er ist.
Wenn der Zustand, wie gesagt, nach Einlesen von W ein Endzustand ist,
dann akzeptieren wir, ansonsten akzeptieren wir nicht.
Das ist noch mal dargestellt mit unseren beiden Möglichkeiten
Zustandstafel oder Zustandsdiagramm.
Wir haben die Übergangsfunktion, die zu jedem Zustand angibt, wie wir
unter einer bestimmten Eingabe einen Folgezustand definieren.
Dann bekommen wir also hier den Zustand SK und das ist also jetzt eine
etwas vereinfachte Übergangstafel.
Wir haben nur noch einen Wert in jedem Feld hier drin.
Zu jedem Zustand und jedem Eingabesymbol bekommen wir den Folgezustand
und das Ganze können wir auch grafisch visualisieren im
Zustandsdiagramm.
Wie vorher auch, werden also der Anfangszustand mit einem eingehenden
Pfeil charakterisiert, der Zustandsübergang nur noch mit den Angaben,
also die Knoten mit dem Zustand drin, Zustandssymbol drin, die
Übergänge durch ein Eingabesymbol charakterisiert.
Der Endzustand wird also durch so einen doppelten Kreis
charakterisiert, dann wissen wir, das ist ein Endzustand und wenn wir
mehrere Übergänge haben, die den gleichen oder mehrere Eingabesymbole
haben, die den gleichen Übergang bewirken, dann schreiben wir die
meistens mit so einem Schrägstrich dazwischen, dass wir wissen, wie
wir weitergehen können.
Und so kommen wir dann also zu dem Begriff einer Konfiguration.
Warum brauchen wir eine Konfiguration?
Was ist das?
Die Konfiguration gibt uns folgendes an, der Automat ist eine Weile
gelaufen, wir sind an einer bestimmten Stelle auf dem Band angelangt,
sind in einem bestimmten Zustand und wollen eigentlich wissen, was
wird der Automat im weiteren Verlauf noch tun.
Damit ich weiß, was er im weiteren Verlauf noch tun wird, muss ich
wissen, was steht eigentlich hier noch ansonsten auf dem Band drauf,
was ich noch nicht gelesen habe.
Also ich muss mir anschauen, den aktuellen Zustand ist und das zu
verarbeitende Restwort.
Wenn ich das beides kenne, kann ich sagen, dieser Automat wird das und
das und das in der Zukunft noch machen, bei der Verarbeitung des
Restwortes.
Und dann kann ich von einer Konfiguration auf eine weitere übergehen.
Ich bin in einem Zustand, habe ein Symbol E unterm Lesekopf, einen
gewissen Rest rechts daneben stehen, dann ist die Folge- konfiguration
die Konfiguration, die ich erreiche, wenn ich in den Folgezustand bei
Eingabe von E im Zustand S übergegangen bin und dann muss ich die
restlichen Zeichen noch lesen.
Ich kann also das Verhalten eines Automaten beschreiben als eine Folge
von Konfigurationen.
Die Übergänge, die durch ein Wort bewirkt werden, sind also oder
bewirken Folgen von Konfigurationen.
Ich betrachte dann eine sogenannte reflexiv-transitive Hülle dieser
Relation.
Das hier ist eine Relation auf solchen Konfigurationen.
Ich kann das erweitern.
Sie erinnern sich daran, dass Frau Mostagi mit voriges Mal etwas
erzählt hat über die Erweiterung einer Übergangsfunktion auf Wörter.
Da war dann Delta-Stern von S, W.
Die einfache Erweiterung einer solchen Funktion, die war von, das war
die Funktion von S kreuz E auf S, war erweitert worden zu einer
Funktion von S kreuz E Stern auf S.
Ganz einfach erweitert worden und genauso macht man das hier.
Das ist also die Übergangsfunktion Delta zu Delta-Stern erweitert
worden.
Genauso macht man das hier mit so einer Relation, dass man die einfach
auf Folgen erweitert.
Dann habe ich hier die reflexiv-transitive Hülle, ist eine eindeutige
Erweiterung.
Also das heißt, jede Konfiguration ist mit sich, ist also mit sich
selbst in dieser Relation und wenn A und, also von A übergehe auf B
und oder hier Stern und von B gehe ich mit Stern über auf C, dann gehe
ich auch von A mit dieser Folgekonfiguration oder mit diesem
Übergangsrelation auf C über.
Das kennen Sie auch von den Ableitungsfolgen, die wir letztes Mal
gemacht haben.
Also das ist nichts Besonderes, nur eine vereinfachte Schreibweise
halt für längere Wörter.
Ich kann dann also sagen, dass ich, wenn hier rechts irgendeine Folge
von zwei Wörtern steht, W1 und W2, dann kann ich also den Folgezustand
betrachten bei Eingabe des ersten Teilwortes W1 und dann habe ich
natürlich eine Folge oder eine Reihe von Einzelübergängen, bis ich das
W1 vollständig abgearbeitet habe und dann bleibt das W2 noch übrig.
Das ist eine ganz einfache Notation, nichts mathematisch Schwieriges
dabei und jetzt kann ich endlich definieren, was die Sprache eines
Automaten ist, nämlich ein Automat, ein endlicher Automat akzeptiert
ein Wort, wenn ich beim Start im Anfangszustand bei Eingabe dieses
Wortes W in einem Endzustand lande oder ich kann sagen, ich beginne in
der Anfangskonfiguration S0W und ich eine Folge von Übergängen komme
ich dann auf eine Endkonfiguration S, Lambda.
Lambda wissen Sie ist das leere Wort.
Ich habe also nur noch das leere Wort auf dem Band, also habe alle
Zeichen gelesen und das S ist aus F.
Die beiden Definitionen sind äquivalent.
Wir wissen also jetzt, wann ein Wort akzeptiert wird und damit kann
ich auch die Sprache definieren für einen Automaten, die habe ich
jetzt, steht hier noch nicht, also die Sprache eines Automaten ist
dann, hier steht es ja, die Sprache des Automaten ist natürlich die
Menge aller Wörter, wie gesagt, die von dem Automaten akzeptiert
werden.
Jetzt habe ich also eine Sprache charakterisiert durch einen
Automaten.
Letztes mal hat Frau Moster gezeigt, wie man eine Sprache durch eine
Grammatik charakterisieren kann.
Wir haben jetzt also eine akzeptieren, eine analysierende Beschreibung
einer Sprache.
Das wird ein Wort analysiert durch den Automaten und anschließend sagt
der Automat, ob das Wort akzeptiert wird oder nicht.
Deswegen ist dies eine analysierende Beschreibung einer Sprache über
solche Akzeptoren.
Hier nochmal ein einfaches Beispiel.
Wir haben hier einen Automaten.
Die Frage ist, welche Sprache wird dadurch charakterisiert?
Das ist also das Zustandsdiagramm hier, die Zustandstafel von einem
Anfangszustand S0, gekennzeichnet diesen Pfeil.
Merken Sie sich bitte, wenn Sie mal irgendwann in die Situation
kommen, dass Sie Automaten aufschreiben müssen.
Gibt ja solche Situationen in Übungsaufgaben oder auch mal in der
Klausur und Sie werden gebeten, einen Automaten vollständig anzugeben.
Das Zustandsdiagramm.
Dann müssen Sie den Anfangszustand mit diesem Pfeil charakterisieren.
Wenn Sie den Pfeil nicht da drin haben, haben Sie keinen
Anfangszustand angegeben.
Sie müssen den Endzustand charakterisieren durch einen Doppelring.
Ansonsten haben Sie keinen Endzustand angegeben.
Das sind alles so Kleinigkeiten.
Und er muss natürlich vollständig definiert sein.
Also von S0 aus können wir hier für die beiden Eingaben A und B
verschiedene Dinge machen.
Unter A bleiben wir bei S0, mit B gehen wir nach S1, mit A gehen wir
wieder zurück, mit B gehen wir nach S2, wo wir auch hingekommen wären.
Nee, wenn wir nicht anders hingekommen wären, nur darüber, dass wir
ein B gelesen haben, darüber gelaufen sind und noch ein B, kommen wir
nach nach S2.
Das heißt, wir müssen mindestens zwei B gelesen haben, um von S0 nach
S2 zu kommen.
Sie können nicht von S0 direkt nach S2 kommen.
Wenn Sie nach diesen zwei B ein A lesen, sind Sie zurück bei S0.
Wenn Sie weiterhin B lesen, bleiben Sie bei S2.
Das heißt, im Zustand S2 haben Sie ein Wort gelesen, das Sie bis dahin
gelesen haben und hier hinten, wenn Sie also im Zustand S2 sind, dann
stehen hier hinten mindestens zwei B, vielleicht noch mehr, kann auch
ein A dahinterstehen, aber wenn hier weniger als zwei B stehen am
Ende, sind Sie garantiert nicht im Zustand S2.
Und das heißt, dass die Sprache, die hier rauskommt, hier sind also
zwei Beispielwörter angegeben mit den Zustandsübergängen oder mit den
Konfigurationsübergängen, bei denen man nacheinander die Zeichen
liest, erst das B, dann das B, dann das A, dann das B, dann das B und
dann ist man im Zustand S2, weil wir zwei B gelesen haben.
Dieses Wort A, B, B, A, B, B gehört zur Sprache.
Das Wort B, A, B, A ist natürlich nicht in der Sprache, weil wir hier
am Ende keine zwei Bs haben, kann man sich leicht angucken, wenn wir
das B lesen, kommen wir im Zustand S1, lesen das A, kommen im Zustand
S0 zurück, lesen das B, sind wieder im Zustand S1, lesen ein A, sind
zurück im Zustand S0, haben nichts mehr zu lesen und sind damit fertig
mit der Analyse des Wortes.
Das Wort ist nicht in der akzeptierten Sprache.
Also ist die Sprache genau die Menge aller Wörter, die auf mindestens
zwei Bs enden.
Also, durch den einfachen Automaten angegeben, jetzt haben wir hier
noch einen anderen Automaten, der folgendes macht, der bleibt so lange
im Zustand S0, wie wir Nullen sehen, sobald eine 1 kommt, geht er in
S1, wenn wir eine weitere 1 sehen, geht er zurück nach S0.
Das heißt, wir sind im Zustand S0, wenn wir überhaupt keine Nullen
gesehen haben oder mindestens zwei oder mindestens vier oder
mindestens sechs oder mindestens acht, also eine gerade Zahl von
Einsen, im Zustand S1 kommen wir nur über eine Eins, drei Einsen, fünf
Einsen und so weiter, also über eine ungerade Anzahl von Einsen.
Und damit haben wir hiermit hier sofort einen Automaten, dessen
Übergangstabelle so aussieht, bei dem wir halt entsprechend, da sind
hier ein paar Beispiele angegeben, die sehr einfach sind, halt immer
mit einer ungeraden Zahl von Einsen in den Endzustand kommen.
Das heißt, das ist die Paritätsfunktion für ungerade Parität.
Ja, wir gucken nach, ist die Anzahl der Einsen ungerade, dann
akzeptieren wir dieses Wort.
Also, so kann man aus den Automaten sehr einfach die Sprachen angeben,
die von solchen Automaten akzeptiert werden.
Und jetzt habe ich hier noch eine andere Situation, ich möchte jetzt
zu einer Sprache den Automaten finden.
Vorher waren die Beispiele so, dass wir gesagt haben, wir haben
Automaten und wollen dafür die Sprache herausfinden.
Jetzt gehen wir uns eine Sprache vor und wollen dafür einen Automaten
charakterisieren.
Also, erster Schritt sieht so aus.
Wie sieht die Sprache aus?
Hier, wir haben eine Sprache, die enthält AA oder BB.
Das heißt, jedes Wort aus dieser Sprache soll so aussehen, dass
irgendwo hier ein AA auftaucht, an irgendeiner Stelle.
Oder kann auch sein, dass irgendwo an irgendeiner Stelle ein BB
auftaucht.
Was davor und was dahinter passiert, interessiert uns gar nicht.
Ja, der einfachste Fall ist natürlich, dass wir mit einem A anfangen,
dann wissen wir, wir müssen unterscheiden, ob wir mit A oder B
anfangen.
Zwei verschiedene Zustände.
Deswegen schreiben wir hier S1 hin und S2.
Und jetzt wollen wir akzeptieren, wenn noch ein weiteres A folgt auf
dieses A.
Das heißt, dann können wir akzeptieren.
Genauso können wir, wenn wir ein B gelesen haben, noch ein weiteres B,
können wir auch akzeptieren.
Jetzt ist der Automat noch nicht fertig.
Wir haben zwar für S0, für A und B gesagt, was wir da machen.
Wir haben für S1 aber nur gesagt, was wir machen, wenn wir ein A
lesen.
Was passiert, wenn wir hier ein B als Eingabe bekommen ist in S1?
Dann würden wir doch die gleiche Situation haben, als wenn wir von S0
nach S2 gegangen sind.
Das heißt, wenn wir hier ein B lesen, gehen wir einfach in S2 und
gehen mit B ja von da aus weiter.
Und wenn wir in S2 ein A lesen, gehen wir einfach hier hoch nach S1.
Und da zählt noch bei Zustand S3, was machen wir denn da?
Na, da ist ja völlig egal, was passiert.
Wenn wir in Zustand S3 gelandet sind, dann haben wir bereits
mindestens einmal die Situation A, A gesehen oder die Situation B, B.
Entweder über diesen Weg, das A, A oder über diesen Weg.
Und bei dem B analog entweder hier unten rum oder über diesen Weg.
Wir haben also A, A gesehen oder B, B.
Und das heißt, hier können wir im Prinzip dann mit A und B bei dem S3
bleiben.
Und das ist genau das, was hier im zweiten Schritt passiert.
Das ist dann der Automat, wie er richtig aufgemalt ist.
Der Automat akzeptiert alle Wörter, die entweder ein A, A oder ein B,
B enthalten oder auch beides, das ist ja egal.
Darauf kommt es nicht mehr an.
Eins von beiden muss drin sein.
Gut, das also zu der Situation.
Dann gibt es eine Reihe Fragen, die man sich stellen kann.
Kann das leere Wort zur Sprache eines Automaten gehören?
Was meinen Sie?
Oh, der steht schon dahinter.
Ja, ganz einfach.
Einfacher Automat, der das leere Wort akzeptiert, da hätten wir einen
Zustand dessen oder ein Automat, der einen Anfangszustand hat, der
bereits Endzustand ist.
Da brauche ich nichts einzugeben und ich akzeptiere bereits das leere
Wort.
Wenn der Anfangszustand Endzustand ist, dann akzeptiere ich das leere
Wort.
Gibt es endliche Automaten, deren Sprache eine endliche Menge ist?
Gibt es, zeige ich Ihnen gleich ein Beispiel.
Sind alle endlichen Mengen Sprachen eines endlichen Automaten?
Kann ich auch einfach Ja darauf sagen.
Ich kann zu jeder Menge, endlichen Menge von Wörtern einen Automaten
konstruieren, der genau diese Wörter akzeptiert, muss ich nur
entsprechend, also wenn ich hier das Wort Ja akzeptieren will, dann
muss ich halt einfach von einem Zustand mit J in einen neuen Zustand
gehen und dann mit A in einen neuen Zustand.
Das muss ein akzeptierender Zustand sein und das war mein
Anfangszustand.
Dann habe ich das Wort Ja akzeptiert.
Ja und ich muss für alle anderen, muss ich dann irgendwie sagen, für
alle anderen Zeichen gehe ich in einen Zustand, der kein Endzustand
ist und in dem bleibe ich.
Dann habe ich nur das Wort Ja akzeptiert.
Und wenn ich jetzt andere Wörter noch akzeptieren möchte, muss ich
entsprechend für jedes solche Wort auch noch eine Zustandsfolge machen
und kann dann dementsprechend akzeptieren.
Schauen wir uns hier dieses Beispiel an.
Ein Automat, der zwei Eingabesymbole hat, A und B.
Der hat hier den Anfangszustand als Endzustand, das heißt, das leere
Wort Lambda ist auf jeden Fall drin und dann kann er mit einem B auf
Zustand S2 kommen und hat dann das Wort B akzeptiert und von dem
Zustand S2 kann er nur noch weggehen mit A und B auf S1 und wenn er in
das 1 gelandet ist, dann bleibt er dort ewig und kann nichts mehr
akzeptieren.
Das heißt, ich habe hier als einfache Sprache eine, die zwei Wörter
enthält, Lambda und B.
Das sind die einzigen beiden Elemente, die ich hier akzeptieren kann.
Und noch ein Beispiel für einen Automaten.
Also ich möchte hier, ich habe eine Sprache A, B, C.
Ich suche einen endlichen Automaten, der nach jedem A genau ein B
akzeptiert.
Nach jedem A genau ein B.
Also ich habe ein A, ein B dahinter.
Ein A, dann nach einem B.
Hier habe ich überhaupt kein A drin, das heißt, nach jedem A steht
genau ein B.
Ist sicherlich drin.
Hier nach diesem A steht ein B.
Also diese drei Wörter gehören dazu.
Diese Wörter hier gehören nicht dazu, weil ich hier nach dem A zwei Bs
habe, nach dem A ein C und nach dem A ein A und nach dem A zwei Bs.
Also das stimmt, diese Wörter sind nicht in der Sprache.
Das muss ich einen Automaten finden, der genau diese Wörter
akzeptiert.
Und wie baue ich den auf?
So wie hier angedeutet, ich kann also, solange ich nur Bs oder Cs
sehe, sagen, die Wörter werden alle akzeptiert.
Wenn ich dann nach einem B oder C ein A sehe, weiß ich, jetzt muss ich
aufpassen.
Nach dem A darf nur ein B kommen.
Ich bin also in einem Zustand S1.
Wenn dort ein B kommt, bin ich im Zustand S2.
Das ist mein Endzustand und ich bin zufrieden.
Wenn aber danach was anderes kommt als ein B, ein A oder C danach
kommt, bin ich in einem Zustand, aus dem ich nicht wieder rauskomme.
Ich darf nicht akzeptieren.
Wenn nach dem B ein A kommt, habe ich wieder die Situation, ich habe
ein A bekommen und muss gucken, kommt danach nur ein B.
Wenn nach dem B ein zweites B kommt, muss ich auch hier unten
reingehen.
Wenn nach dem B ein C kommt, dann gehe ich wieder zurück,
Anfangssituation.
Bleibt dort so lange, bis ich wieder ein A sehe und bin entsprechend
wieder in der Situation hier vorne.
Also das ist ein ganz einfach konstruierter Automat und Sie werden
Übungen darin bekommen, solche Automaten zu konstruieren, an einfachen
Beispielen.
Wir kommen zu dem nächsten Punkt, den nicht deterministischen
endlichen Automaten.
Warum nicht deterministischen?
Was war denn hier deterministisch?
Also deterministisch war doch, das hieß doch, wir haben zu jedem
Zustand, für jede Eingabe einen eindeutigen Folgezustand.
Also wenn wir hier von einem Zustand S ausgingen, irgendeine Eingabe
E, dann kam da irgendein Folgezustand S' raus.
Nicht-Determinismus könnte bedeuten, dass wir eine Auswahl haben.
Mit einem Zeichen E könnten wir auf S' oder S2' oder S3' gehen.
Das wäre ein Nicht-Determinismus.
Es ist nicht bestimmt, nicht eindeutig bestimmt, was der Folgezustand
ist.
Das heißt, wir haben eine gewisse Unsicherheit über den Folgezustand.
Die Frage ist, bringt das irgendwas?
Braucht man das?
Wir werden sehen, dass das gewisse Vorteile hat.
Also zunächst mal definieren wir einen nicht-deterministischen
endlichen Automaten.
N-E-A.
Also der E-A ist immer deterministisch.
N-E-A, hier so kurz geschrieben, ist ein nicht-deterministischer
endlicher Automat ohne Ausgabe.
Die mit Ausgabe, das waren die Miele- und Uhrautomaten, die
interessieren uns im Augenblick nicht mehr.
Wir wollen nur Akzeptoren angucken.
Und der Unterschied ist, dass jetzt die Übergangsfunktion von S kreuz
E geht in die Potenzmenge von S.
Also Menge aller Teilmengen von S.
Dieses komische Symbol hier ist ein P von S, Potenzmenge von S.
Das heißt, wir haben hier irgendeine Menge von Folgezuständen.
Der ist also nicht eindeutig.
Es kann auch sein, dass wir die leere Menge hier haben.
Das heißt, es kann sein, dass wir gar nicht weitermachen können von
einem Zustand aus.
Die Frage ist, was bringt uns das?
Offensichtlich hat das ja viel mehr Möglichkeiten.
Und die Frage ist, bringt uns das etwas in Bezug auf die
Sprachmächtigkeit.
Kann ich damit andere Sprachen akzeptieren, als mit einem
deterministischen Automaten?
Das werden wir uns genauer angucken.
Kleines Beispiel.
Hier haben Sie ein kleines Beispiel eines Automaten, der nicht
deterministisch ist.
Wir haben nämlich hier ausgehend von S0, bei Eingabe von A als
Folgezustände S0 oder S1, bei Eingabe von B S0 oder S2.
Das sehen Sie hier an dem Diagramm auch.
Wenn wir S0 haben, dann gibt es zwei Kanten, die mit A gekennzeichnet
sind, die von S0 ausführen.
Eine Kante geht zurück zu S0, die andere geht nach S1.
Bei B geht eine Kante nach S2, die andere geht zurück nach S0.
Und entsprechend hier S1, von S1 ausgehend, haben Sie zwei Kanten, die
mit A beschriftet sind.
Eine geht aus S1 zurück, die andere geht nach S3.
Und wenn Sie sich das anschauen hier bei S2, analog, haben Sie zwei
mit B gekennzeichnete Kanten.
Und von S3 aus können Sie überhaupt nichts mehr machen.
Welche Sprache wird denn von so einem Automaten akzeptiert?
Was heißt denn das?
Wenn wir uns sich das hier nur anschauen und überlegen sich, was kann
der akzeptieren?
Akzeptieren kann er ein Wort, dadurch, dass er in den Endzustand S3
kommt.
Das heißt, er muss mit einem A oder einem B als letzten Zeichen, wenn
wir uns anschauen, wie kann ein solches Wort aussehen?
Das können wir bei zwei Fällen hier betrachtet.
Es kann als letztes Zeichen ein A stehen oder es kann dort ein B
stehen.
Ja, ein A oder ein B.
Das sind die beiden Möglichkeiten, wie ich auf S3 komme.
Was kann davor gewesen sein, bevor ich da hingekommen bin?
Da kann es sein, dass ich hier beliebig oft durchgelaufen bin, bei S1
mit As oder Bs.
Das heißt, hier kann irgendein Wort U gestanden haben und U ist eine
Folge von As und Bs.
Irgendeine beliebige Folge.
Und davor muss ich ja irgendwann auf S1 gekommen sein.
In S1 konnte ich also beliebig lange bleiben, aber davor muss ich ja
hingekommen sein von S0 aus.
Das heißt, es muss davor auch ein A gewesen sein.
Da konnte ich nur mit A hinkommen, von S0 aus.
Und in S0, jetzt habe ich das hier, jetzt schreibe ich hier, wollte ja
eigentlich ein V hinschreiben und hier ein U.
Also, ich habe hier U und V sind einfach Wörter aus As und Bs,
beliebige Wörter.
Das heißt, ich bin hier beliebig lange rumgelaufen, da beliebig lange
rumgelaufen, aber einmal muss ich von S0 nach S1 gekommen sein.
Das ist dieses A und dann am Ende muss ich mit einem A auf S3 gekommen
sein.
Solche Wörter können akzeptiert werden.
Das heißt, das letzte Zeichen ist vorher schon einmal aufgetaucht.
Das letzte Zeichen kann ein A oder ein B gewesen sein oder hier
allgemein formuliert.
Es ist also die Menge aller Wörter von diesem Automaten akzeptiert,
bei denen das letzte Zeichen vorher schon einmal vorgekommen ist.
Also hier irgendein V-Strich, B, U-Strich.
Das heißt, wir haben irgendwelche Wörter hier drin, bei denen das
letzte Zeichen vorher schon einmal aufgetreten ist.
Das ist genau dieser Automat.
Sehr einfach formuliert.
Das Zeichen, was mich zum Endzustand führt, muss vorher schon einmal
aufgetaucht sein.
Mir steht er nicht.
Das ist jetzt ein nichtdeterministischer Automat.
Es ist nur die Frage, wie kann ich eigentlich so ein
Übergangsverhalten für nichtdeterministische Automaten definieren?
Wie kann ich die Sprache definieren, die akzeptiert wird von einem
nichtdeterministischen Automaten?
Ich musste ja immer sagen, ich bin von einem, wenn ich ein Wort
eingebe, komme ich zu einem Endzustand.
Jetzt gebe ich ein Wort ein und habe, ja, wo komme ich eigentlich hin?
Ich komme ja auf viele, viele mögliche Zustände.
Das heißt, wenn ich ein Wort betrachte, das ich eingebe, muss ja die
Erweiterung machen auf Wörter, dann schaue ich mir an, wohin komme
ich, wenn ich das erste Zeichen eingebe.
Da komme ich auf irgendeine Menge Delta von S, E.
Das ist hier diese ganze Menge.
Das erste Zeichen des Wortes eingegeben, habe ich eine Menge von
Folgezuständen.
Und jetzt gebe ich das restliche Wort W ein hier.
Das erste Zeichen war E, da kommen noch eine Reihe weiterer Zeichen.
Jetzt ist die Frage, welchen nehme ich denn jetzt?
Von wo aus mache ich den jetzt weiter?
Ich muss natürlich von jedem beliebigen Zustand aus in dieser Menge
weiter gucken.
Ich nehme also zum Beispiel hier einen S-Strich raus und schaue mir
an, wo komme ich hin, wenn ich von S-Strich aus mit einem Wort W
weiterlaufe.
Das ist jetzt im Prinzip rekursiv definiert.
Für S, Lambda, also für Eingabe des leeren Wortes, bleibe ich in dem
Zustand.
Das ist also die Menge, die nur den Zustand von S enthält.
Hier mache ich das jetzt für Wörter der Länge K plus 1, also E, W.
W ist ein Wort der Länge K.
Und für Wörter der Länge K habe ich bereits definiert, wie dort die
Folgezustandsmenge aussieht.
Das ist eine einfache rekursive Definition.
Eindeutige Fortsetzung, genau wie vorher auch.
Und es ist offensichtlich, ich muss natürlich von jedem beliebigen
Zustand aus mir anschauen, wie sieht die Folgemenge aus.
Also von jedem Zustand aus die ganzen Folgenmengen betrachten und ich
muss die alle vereinigen.
Also Delta-Stern von S, E, W ist gleich Delta-Stern von dem
Folgezustand Delta-S, E, W, beziehungsweise dieses Delta-S, E ist eine
Menge von Zuständen.
Deswegen ist das die Vereinigung aller Delta-Stern von S, W für S' aus
Delta von S, E.
Delta von S, E ist diese Menge, die ich hier angedeutet hatte.
Ich muss also für jeden Zustand aus mir das Delta-Stern von S', W
angucken und die Vereinigung aller dieser Mengen ist dann meine
Folgezustandsmenge.
Das kann also eine Riesenmenge sein.
Kann auch eine kleine Menge sein.
Hängt davon ab, was ich für eine Zustandsmenge oder für eine
Zustandstafel habe.
Das ist also wieder die einfache Fortsetzung meiner Übergangsfunktion,
die zunächst nur für einzelne Zeichen definiert ist, auf Wörter.
Es gibt wieder nur eine einzige sinnvolle Art, das zu definieren.
Eine natürliche Fortsetzung, induktiv definiert auf diese Art und
Weise, beginnend also mit dem leeren Wort und dann sukzessive
erweitert für längere Wörter.
Durch diese Gleichung.
Das ist standardinduktive Definition.
Schauen wir uns das an für unseren Beispiel, das wir gerade hatten.
Das Beispiel, wo wir die Menge aller Wörter hatten, deren letztes
Zeichen schon mal vorher aufgetreten war.
Wenn wir uns jetzt anschauen, Delta-Stern von S0, A, B.
Die beiden Zeichen A und B werden eingegeben.
Es steht hier, das ist S0, S1, S2.
Warum ist das der Fall?
Betrachten wir uns Delta von S0, A.
Delta von S0, A ist diese Menge, S0, S1.
Wenn wir also jetzt auf diese Menge, das Symbol B, anwenden, müssen
wir von S0 und S1 aus das Symbol B eingeben und kommen dann auf die
Menge S0, S2 und S1.
Das heißt insgesamt auf die Vereinigung dieser beiden Mengen.
Und das ist gerade das, was hier steht.
Also S0, S1, S2.
Auf die Art und Weise werden die Mengen immer größer.
Wir haben also eine ziemliche Unsicherheit über den tatsächlichen
Zustand.
Denn in der Realität wird natürlich ein Automat immer nur in einem
dieser Zustände übergehen.
Wir sagen nur, er könnte in irgendeinem beliebigen dieser
Nachfolgezustände übergehen.
Das kann man auch noch erweitern, man macht daraus einen
stochastischen Automaten, damit eine gewisse Wahrscheinlichkeit in
irgendeinen Folgezustand übergeht.
Das werden wir aber gar nicht hier betrachten.
Das wäre noch eine Erweiterung der Betrachtung von eigentlichen
Automaten, dass man noch stochastische Automaten betrachtet.
Auch eine interessante Sache.
Sie lernen etwas ähnliches kennen, wenn Sie Markov-Prozesse
kennenlernen.
Markov -Prozesse sind im Prinzip so etwas Ähnliches wie stochastische
Automaten.
Ich muss natürlich noch etwas definieren.
Wir hatten, um bei einem endlichen Automaten die Sprache angeben zu
können, die akzeptiert wird von dem Automaten, hatten wir
Konfigurationen betrachtet.
Also, wir hatten eine Startkonfiguration, S0, W.
Ich nehme das mal hier ein E hin, ein Zeichen E, wo das erste ist
eingegeben.
Das ist unsere Startkonfiguration.
Und dann waren wir einfach übergegangen auf irgendeinen, das war der
Konfigurationübergang, auf irgendeinen S, W.
Und das S war gerade Delta von S0, E.
Das geht jetzt ja nicht mehr so einfach.
Jetzt könnte es ja sein, dass es noch mehrere gibt.
Könnte sein, dass hier noch ein S-Strich ist und W.
Und vielleicht noch irgendein S2-Strich und W.
Wenn diese S, S-Strich und S2-Strich alle in Delta von S0, E drin
sind.
Also, ich muss jetzt aus einer Konfiguration, S, E, W.
Das heißt, ich habe bei meinem Automaten, das ist mein Automat mit
diesem Eingabeband und dem Lesekopf und der ist hier auf irgendeinem
Feld.
Da steht ein E und der Rest des Bandes hier ist W.
Das, was links davon ist, haben wir alle schon gesehen.
Also alles, was wir noch betrachten müssen, um sagen zu können, wohin
wird der Automat am Ende laufen.
Von so einer Konfiguration aus, also hier sind wir im Zustand S, ist
eine mögliche Folgekonfiguration S-Strich, W.
Für ein S-Strich aus Delta von S, E.
Also ein möglicher Folgezustand bei Eingabe von E in den Zustand S.
Und das W ist halt gerade entsprechend der Rest hier von dem Wort.
Also dann bin ich ja eins weiter gelaufen und komme dahin.
Das heißt, ich habe hier nicht mehr eine eindeutig definierte
Folgekonfiguration, sondern ich habe mehrere.
Und von da aus kann ich jetzt genauso eventuell mehrere solche
Folgekonfigurationen haben.
Das Ganze kann ich beliebig oft anwenden.
Dann habe ich wieder die reflexiv-transitive Hülle.
Das kennen Sie alles bereits, die einfache Fortsetzung.
Transitiv machen der Relation und reflexiv machen.
Das sind Dinge, die Sie bereits kennen.
Und jetzt betrachten wir wieder unser Beispiel.
Wir haben hier ein Eingabewort BBAB.
Offensichtlich ein Wort, das zu unserer Sprache gehört.
Denn das Zeichen B taucht vorher schon mal auf.
Sogar mehrfach.
So, fangen wir also an mit S0BBAB.
Wir wollen ja feststellen, kommen wir in eine Endkonfiguration, wo wir
sagen können, jetzt wird das Wort akzeptiert.
Das wäre interessant.
Mögliche Konfigurationsfolgen von S0BBAB.
Wir lesen ein B.
Wir könnten in S0 bleiben.
Wir lesen ein B.
Wir könnten in S0 bleiben.
Wir lesen ein A.
Wir könnten in S0 bleiben.
Wir lesen ein B.
Wir könnten in S0 bleiben.
Wir haben nichts mehr zu lesen, sind im Anfangszustand.
Dürfen wir das jetzt akzeptieren?
Wir sind ja immer noch im Anfangszustand.
Wir können eine Aussage über das Akzeptierungsverhalten nur machen,
wenn wir eine Aussage haben, wir kommen in einen Endzustand oder
kommen nicht in einen Endzustand.
Schauen wir uns die anderen Möglichkeiten an.
Ich könnte ja mit dem B auch in S2 rüber gehen.
Ja, da steht, ich kann nach S0 oder S2.
Und wenn ich dann wieder ein B lese, dann S2 und B, dann gehe ich
einfach nach S3 und dann lese ich immer noch, habe ich immer noch A
und B auf meinem Band.
Ich bin im Endzustand, habe aber rechts neben meinem Lesekopf immer
noch Zeichen, die ich noch nicht gelesen habe.
Aber von S3 aus gibt es keine weiteren Übergänge, ich bin in der
Sackgasse.
Ich bin noch nicht fertig mit dem Lesen meines Wortes, bin in einem
Zustand, von dem ich nicht weitermachen kann.
Kann also nicht sagen, dass das eine Endkonfiguration ist, weil ich
nicht alles gelesen habe.
Es gibt zum Glück noch eine andere Möglichkeit.
Ich kann also von S0 aus mit B in S0 bleiben.
Ich lese B, gehe nach S2, lese A, bleibe einfach in S2, lese noch ein
B und gehe nach S3.
Jetzt habe ich alle Zeichen gelesen, habe das leere Wort in der
Konfiguration drin, das heißt rechts neben meinem Lesekopf steht
nichts mehr, was ich lesen muss und ich bin im Endzustand.
Das heißt, als Konsequenz für die Art, wie wir hier das
Akzeptierungsverhalten beschreiben werden, wenn es eine Folge gibt,
eine Möglichkeit gibt, durch unseren Baum von Konfigurationsfolgen
hier durchzulaufen und ich komme hier in eine Konfiguration, wobei der
Zustand ein Endzustand ist, irgendein SE oder SF und ich habe nichts
mehr zu lesen auf dem Band.
Wenn es einen solchen Weg gibt, dann werde ich sagen, dieses Wort kann
ich akzeptieren.
Es gibt eine Möglichkeit, ausgehend vom Anfangszustand auf einen
Endzustand zu kommen und wenn es eine solche Möglichkeit gibt, dann
sage ich, das ist ein Wort, das ich akzeptieren kann.
Wenn ich Pech habe, habe ich hier irgendeine Folge, bei der ich gar
nicht durchlaufe bis zum Endzustand, dann muss ich gucken, gibt es
eine andere Möglichkeit, sodass ich zum Endzustand kommen kann.
Und wenn es keine solche Möglichkeit gibt, in der Menge aller
möglichen Folgekonfigurationen, bei Eingabe eines Wortes W, wenn es
keine solche Möglichkeit gibt, auf eine Endkonfiguration zu kommen,
wobei der Zustand ein Endzustand ist und das Restwort leer ist, das
heißt, ich habe alles gelesen, dann habe ich nicht akzeptiert.
Also, der Automat akzeptiert ein Wort, wenn die Menge der erreichbaren
Zustände von dem Zustand S0 aus, bei Eingabe von W, mindestens einen
Endzustand enthält.
Oder, das ist das, was hier steht, ich schneide die Menge der
Folgezustände von S0 bei Eingabe von W mit der Menge der Endzustände,
wenn ich dabei einen Endzustand drin habe, dann sage ich, das Wort
wird akzeptiert.
Und das kann ich mit den Konfigurationen auch so ausdrücken, dass ich
anfangend mit der Anfangskonfiguration S0, W eine Möglichkeit habe,
auf einen Zustand zu kommen, S, aus der Menge der Endzustände, mit
einem Restwort Lambda auf dem Band, das heißt, ich habe alles gelesen.
Das ist also jetzt die Definition, wie ich ein Wort akzeptieren kann,
wie ich die Sprache definieren kann, für einen nichtdeterministischen
Automaten.
Und jetzt kann ich die interessanten Fragen stellen.
Ich hatte gesagt, zu Anfang, als ich Nichtdeterminismus eingeführt
habe, naja, ich möchte doch sehen, ist der Nichtdeterminismus etwas,
was mir mehr Möglichkeiten bietet, als der Determinismus.
Offensichtlich kann ich ja mehr machen.
Da habe ich jetzt so Mengen oder irgendwelche Folgen von
Konfigurationen und es kann sein, dass einige Konfigurationsfolgen
nicht zum Endzustand führen, eine führt zum Endzustand, dann sage ich,
dann akzeptiere ich das Wort.
Das sieht doch so aus, als wenn ich mehr machen kann.
Und die Frage ist also, wenn ich einen nichtdeterministischen
endlichen Automaten a' habe, gibt es einen äquivalenten endlichen
Automaten, also deterministischen Automaten a', äh, a',
Entschuldigung.
Also gibt es einen dazu äquivalenten deterministischen Automaten.
Die andere Richtung ist natürlich trivial.
Wenn ich einen deterministischen Automaten habe, dann ist der ja
insbesondere nichtdeterministisch.
Ja, weil ich immer nur einen Folgezustand habe, das heißt, ich könnte
im Prinzip die Menge aus diesem Folgezustand hinschreiben.
Dann habe ich nichtdeterministischen Automaten daraus gemacht, das ist
trivial.
Also ich finde immer einen äquivalenten nichtdeterministischen
endlichen Automaten, der die gleiche Sprache akzeptiert wie ein
deterministischer endlicher Automaten.
Und äquivalent heißt eben, akzeptiert die gleiche Sprache.
Aber andersrum ist es nicht so offensichtlich, muss man sich ein
bisschen mehr überlegen.
Und ich verrate natürlich gleich, dass das tatsächlich geht.
Ich kann zu jedem nichtdeterministischen endlichen Automaten einen
äquivalenten endlichen Automaten definieren, der deterministisch ist.
Und dazu muss ich einfach die Mengen von Zuständen meines
nichtdeterministischen Automaten als neue Zustände definieren.
Das heißt, wir betrachten einfach Mengen von Zuständen.
Ich habe also jetzt ein Automat A2 zu einem Automaten A1.
Dieser Automat A2 hat eine Zustandsmenge, das ist einfach die
Potenzmenge von S.
Mein Gott, ich habe beim nichtdeterministischen endlichen Automaten N
Zustände.
17 Zustände.
Wenn ich die Potenzmenge betrachte, wie ist denn, wenn S hat N
Zustände.
Die Potenzmenge von S hat dann wie viele Zustände?
Was meinen Sie?
Ja, N Fakultät meinen Sie.
Das wäre zu wenig.
N Fakultät wäre ja einmal, zweimal, dreimal, viermal, fünfmal und so
weiter.
Also Produkt aller Zahlen von 1 bis N.
Wenn ich alle möglichen Teilmengen betrachte, einer Menge N, dann ist
das gerade die Mächtigkeit 2 hoch N.
Ja?
Das ist die Anzahl der Teilmengen einer Menge von N Zuständen.
Sie können ja im Prinzip, wie kann man sich das überlegen?
Sie haben ja die N Elemente.
Wenn Sie hier die N Elemente haben, 1 bis N, dann müssen Sie, um die
Potenzmenge angeben zu können oder eine Menge spezifizieren zu können,
im Prinzip mit 0 oder 1 markieren, ob das Element drin ist oder nicht.
Das heißt, Sie haben alle Möglichkeiten hier an N Positionen 0 oder 1
zu schreiben.
Und das sind gerade 2 hoch N verschiedene Möglichkeiten.
Deswegen 2 hoch N.
Das heißt, ich habe eine exponentielle Explosion meiner Zustandsmenge.
Das zeigt, offensichtlich kann ich mit einem nicht deterministischen
Automaten etwas wesentlich kompakter beschreiben, als mit einem
deterministischen Automaten.
Der muss ja so sehr viel mehr Zustände haben, sofern die alle
gebraucht werden.
Und zum Glück ist es häufig so, dass wir nicht alle brauchen.
Aber im Prinzip wird die Zustandsmenge des deterministischen
Automaten, der das gleiche kann wie ein nicht deterministischer, wird
sehr groß.
Also der Anfangszustand ist einfach die Menge aus dem Anfangszustand
des nicht deterministischen Automaten und das Erstrich ist dann die
Menge aller Teilmengen von S, die einen nicht leeren Durchschnitt
haben mit der Menge der Endzustände.
Das sind dann Endzustandsmengen.
Und das entspricht genau dem, was wir vorhin gesagt haben.
Wenn es einen Weg gibt hin zu einem Endzustand, dann akzeptieren wir.
Deswegen hier das Gleiche.
Wenn ich einen Zustand, also eine Menge von Zuständen habe, da ist ein
Endzustand drin, heißt das, ich könnte ja zu dem Endzustand kommen,
dann ist das ein Endzustand.
Und meine Funktion Delta Strich, die Übergangsfunktion, ist jetzt eine
Übergangsfunktion auf Mengen von Zuständen.
Naja, das ist einfach die Vereinigung aller Delta von SE für S aus T
und T ist diese Menge von Zuständen.
Das ist also eine ganz naheliegende Erweiterung meiner
Übergangsfunktion.
Und damit habe ich so einen neuen Automaten definiert auf den
Teilmengen von S, ausgehend von der Übergangsfunktion meines Automaten
A1.
Und jetzt muss ich schauen, oder man kann sich ziemlich schnell
überlegen, dass dieser Automat das gleiche Akzeptierungsverhalten
haben wird, wie der nicht-deterministische Automat.
Offensichtlich kann diese Menge sehr groß werden.
Hier steht es ja auch, S Strich, die Potenzmenge von S hat zwei hoch N
Elemente.
Und das ist halt eine sehr große Zahl.
Und jetzt betrachten wir das als am Beispiel, wieder unser Automat,
der nicht-deterministisch ist.
Und wir wollen jetzt sehen, wie sähe denn der dazu äquivalente
deterministische Automat aus?
Wir fangen an, wir wissen ja, wir brauchen eigentlich nur die
erreichbaren Zustände zu betrachten.
Alles, was vom Anfangszustand aus erreichbar ist.
Und der Anfangszustand ist in diesem Fall bei unserem äquivalenten
deterministischen Automaten gerade die Menge, die den Zustand S0
enthält.
Von diesem Zustand aus, S0, komme ich auf S0, S1 oder mit A.
Das heißt, das ist hier die nächste Menge.
Das ist einfach.
Brauche ich nur zu übertragen, was in dieser Zeile steht.
Die beiden Einträge.
Jetzt sind das offensichtlich Zustandsmengen, die ich erreichen kann.
Also schreibe ich sie mir jetzt hier hin, als meine beiden neuen
Zustände, die ich auch brauche.
Diese Mengen von Zuständen müssen Zustände des äquivalenten
deterministischen Automaten sein.
S0, S1 und S0, S2.
Jetzt schaue ich mir an, welche Zustände erreiche ich, wenn ich von
diesem Zustand S0, S1 ausgehe.
S0, S1, da komme ich mit A auf S0, S1, S3.
Also habe ich hier S0, S1, S3 und wenn ich mir das mit B anschaue, S0,
S1, S2.
Diese beiden Mengen müssen also auch Zustände meines deterministischen
Automaten sein.
Die schreibe ich mir hier hin.
Jetzt schaue ich mir an, wohin komme ich, wenn ich von S0, S2 starte.
S0, S2, da komme ich auf S0, S1, S2.
S0, S2 komme ich unter B auf S0, S2, S3.
Das heißt, jetzt habe ich hier diese beiden Mengen.
Und habe schon wieder eine neue Menge, nämlich S0, S2, S3 war bisher
noch nicht dabei.
Die kommt dazu.
Und so fülle ich nach und nach diese alle aus.
Habe also hier S0, S1, S3.
Führt also hier auf die beiden.
Die habe ich beide schon drin.
Von S0, S1, S2 komme ich jetzt auf wieder einen neuen Zustand.
S0, S1, S2.
Naja, das sind schon drei von den vier Zuständen drin.
Von denen komme ich auf alle anderen.
Also S0 bis S3.
Das muss ich mir noch weiter anschauen.
Was ist mit den restlichen?
Wohin komme ich, wenn ich von S0, S2, S3 ausgehe?
Wohin komme ich, wenn ich von S0, S1, S2, S3 ausgehe?
Na gut, irgendwo hin komme ich natürlich von.
Von S3 aus komme ich nirgends hin.
Und ich habe also dann hier trotzdem wieder diese Mengen.
Das ist also die Menge aller Teilmengen von S, die ich erreiche, wenn
ich von S0 loslaufe.
Und damit habe ich die Zustände, die ich brauche für meinen
deterministischen Automaten, der äquivalent sein soll zu dem
Ausgangsautomaten.
Das sind weniger in dem Fall als 2 hoch N.
Wir haben hier vier Zustände.
2 hoch 4 wäre 16.
Wir haben hier halt nur 1, 2, 3, 4, 5, 6, 7 Zustände.
Also haben wir nochmal Glück gehabt.
Und wenn wir jetzt hier die betrachten, dann können wir also jetzt
diese Zustandsmengen einfach ersetzen durch die Zustandsbezeichnungen.
Wir haben also dann hier einen neuen Automaten, der jetzt so aussieht,
wie hier angegeben.
Wenn wir uns jetzt zu diesem Automaten das Zustandsdiagramm aufmalen,
dann sieht das so aus, wie hier angegeben.
Das ist jetzt der gleiche oder der äquivalente Automat, der die
gleiche Sprache akzeptiert, wie der nicht-deterministische Automat.
Und Sie werden mir zustimmen, dass der eigentlich deutlich einfacher
war, der nicht-deterministische.
Bei dem konnte man viel schneller sehen, welche Sprache akzeptiert
wird.
Wenn Sie hier feststellen wollen, welche Sprache wird akzeptiert, dann
müssen Sie ein bisschen mehr nachdenken, als Sie bei dem nicht
-deterministischen Automaten nachdenken mussten.
Da sah man das sofort.
Das heißt, die Beschreibung einer Sprache durch einen nicht
-deterministischen Automaten kann wesentlich intuitiver sein, als die
Beschreibung durch einen deterministischen Automaten.
Und deswegen ist es also wichtig, dass man weiß, man kann auch nicht
-deterministische Automaten anschauen.
Und auf diese einfache Art und Weise, die ich Ihnen jetzt dargestellt
habe, können wir tatsächlich einen äquivalenten deterministischen
Automaten jeweils bekommen.
Dass die Menge der Endzustände gerade die ist, bei der wir jeweils
Mengen haben, in denen ein Endzustand drin ist, hatte ich Ihnen schon
mehrfach erläutert.
Das ist also naheliegend, das so zu machen.
Also die sind hier gekennzeichnet, das sind die drei Endzustände
unseres äquivalenten deterministischen Automaten.
Damit sind wir fast fertig mit der Konstruktion.
Es könnte sein, dass man dabei irgendwo bei dieser Konstruktion, die
wir gemacht haben, dass man hier irgendwann auf eine Situation kommt,
dass es nicht weitergeht.
Dass ich nur Zustände erreicht hatte, von denen aus ich nicht
weitermachen kann, weil die Folgezustandsmengen leer sind.
Dann müsste ich auf einen Extrazustand gehen, das ist hier angedeutet.
Also ich habe hier eine Situation, da geht es eigentlich nicht weiter.
Dann definiere ich einfach einen neuen Zustand, der nicht Endzustand
ist, der dann halt ein Sackgassenzustand ist.
Das heißt, alle fehlenden Übergänge führen einfach dorthin.
Ich sage mal, alle restlichen Eingaben führen dann zu diesem Zustand.
Von dem aus kann ich nicht weitermachen und hier ist also mein
eigentlicher Automat.
Und damit habe ich dann alle Situationen deterministisch erfüllt, für
jede Eingabe einen Übergang definiert und ich habe das gleiche Ein
-Ausgabe -Verhalten wie für den nicht deterministischen Automaten.
Ich habe also damit diese Aussage, zu jedem nicht deterministischen
endlichen Automaten A1 gibt es einen deterministischen endlichen
Automaten A2, der die gleiche Sprache akzeptiert und umgekehrt.
Das Umgekehrte war trivial.
Hier steht nochmal ein Beweis.
Wie gesagt, ich denke, der Ansatz ist so naheliegend, ich brauche das
jetzt nicht formal zu beweisen.
Das würde etwas länger dauern, müsste man mit Induktion über die Länge
der eingegebenen Wörter machen.
Aber das will ich mir sparen.
Und die andere Richtung war trivial.
Und damit wissen wir, dass diese Sprachklassen identisch sind.
Die Sprachklassen, bei denen ich deterministische Automaten betrachte
oder nicht deterministische Automaten mit endlich vielen Zuständen,
führen auf die gleichen Sprachklassen, sind also gleich mächtig in
Bezug auf die Ausdrucksfähigkeit.
Also auch die Sprachen von nicht deterministischen Automaten haben
diese Eigenschaft, dass wir dort so eine Pumpstelle drin haben, wie
die Sprachen von deterministischen Automaten auch.
Also, was sind eigentlich die weiteren Vorteile?
Ich hatte schon gesagt, dass die einfachere Darstellung von Automaten
und Akzeptoren hier eine Rolle spielt.
Also stellen Sie sich vor, Sie haben hier irgendeinen Text und Sie
wollen also eine Volltextsuche machen.
Eine triviale Art, wie Sie eine Volltextsuche in einem Dokument machen
können.
Nach irgendeinem Wort, das Sie hier da hinschreiben.
Wenn Sie nach irgendeinem Wort suchen, können Sie ganz einfach einen
Automaten konstruieren.
Nämlich einen Automaten, der so aussieht, dass dieses Wort, nehmen wir
mal an, das ist das Wort E1 bis EN.
Dann schreiben Sie einfach einen Automaten hin, der einen
Anfangszustand hat, von dem aus Sie beliebig weiterlaufen können.
Und dann gibt es hier einen Übergang mit dem Zeichen E1, dann einen
mit E2, dann einen mit E3 und so weiter.
Also wenn Sie zum Beispiel nach dem Wort Automaten suchen, dann würden
Sie hier hinschreiben A, dann hier U, dann da T und dann und so weiter
bis hier E und N.
Das wäre dann also Ihr Wort Automaten, das heißt, dieser Automat ist
in der Lage, nach dem Wort Automaten zu suchen.
Also hier entsprechend weitere Zeichen und er kann natürlich davor
beliebige Zeichen lesen, er kann danach beliebige Zeichen lesen.
Das heißt, er würde diesen ganzen Text hier durchlesen, würde
feststellen, hier ist einmal E1 bis EN bzw.
Automaten und dann würde er hier weiterlesen bis zum Ende.
Das sind genau diese Zustände, die Sie dort hingeschrieben haben.
Das wäre ein Mustererkenner in einer Anwendung, wo wir also nach einem
Text oder nach einem Muster in einem Text suchen.
Für Volltextsuche wäre das ein naiver, trivialer Ansatz.
Sie können in anderen Vorlesungen sich damit beschäftigen, dass man
das noch effizienter machen kann, dass das hier der naive Ansatz ist,
der viel zu viel Zeit kostet, aber es ist so auf eine einfache Art und
Weise beschrieben.
Und Sie können sicher sein, dass Sie das nicht so einfach beschreiben
können mit einem deterministischen Automaten, da müssten Sie ein
bisschen mehr Aufwand reinstecken.
Das können Sie sich gerne selbst überlegen, wie man da den
deterministisch macht, so schwer ist es nicht.
Aber ich wollte nur kurz andeuten, dass das eine Möglichkeit ist, wie
man die anwenden kann.
Eine andere Möglichkeit ist einfach, die deterministischen Automaten
erlauben eine einfache Argumentation über bestimmte Untersuchungen von
Eigenschaften von Automaten.
Zum Beispiel ist man daran interessiert, was passiert eigentlich, wenn
ich zwei Sprachen habe, die von endlichen Automaten akzeptiert werden
können.
Was ist eigentlich mit dem Produkt der beiden Sprachen oder mit der
Vereinigung der beiden Sprachen?
Sind das auch Sprachen, die von entsprechenden Automaten akzeptiert
werden können?
Also ich habe irgendwelche Sprachen L und L', dann ist die Frage, kann
ich eigentlich L vereinigt L', auch von einem endlichen Automaten
akzeptieren, oder L mal L', also das Hintereinanderschreiben von
Wörtern aus L und Wörtern aus L', ist das auch mit einem endlichen
Automaten möglich?
Dazu muss ich einen endlichen Automaten konstruieren.
Und das kann man sich relativ einfach überlegen, ich werde das gleich
an einem Beispiel vorführen, für die Vereinigung von Automaten oder
von Sprachen.
Wir haben also diese beiden Sprachen L und L', und wollen zeigen, L
vereinigt L', die Vereinigung der beiden Sprachen ist auch wieder eine
Sprache, die von einem endlichen Automaten akzeptiert werden kann.
Dann muss ich mir also zwei Automaten hernehmen.
Wieso steht denn da LEA von E, was ist das denn?
Behauptung aus LEA von...achso natürlich, Entschuldigung.
Hier ist also so, dass das LEA von E, nochmal kurz, was war das
nochmal?
Das ist die Menge aller Sprachen, die von endlichen Automaten
akzeptiert werden können, über dem Alphabet E.
Und insofern sagen wir hier, diese beiden Sprachen können von
endlichen Automaten akzeptiert werden.
Also, wenn L eine solche Sprache ist, gibt es einen endlichen
Automaten A, der diese Sprache akzeptiert.
L ist ein L von A.
Genauso gibt es für das L' einen Automaten A', sodass L' gleich L von
A ist.
Die Sprache des Automaten A'.
Und wir nehmen einfach an, ohne Beschränkung der Allgemeinheit, dass
die beiden Zustandsmengen disjunkt sind.
Wenn sie das nicht sind, machen sie die einfach disjunkt, indem sie
die umbenennen.
Gar kein Problem.
Also das kann man immer annehmen, dass die disjunkt sind.
Und jetzt definieren wir einfach den endlichen Automaten, der die
Vereinigung der beiden Sprachen akzeptiert, indem wir einen Automaten
konstruieren aus diesen beiden Automaten A und A', der die beiden
Sprachen akzeptiert.
Also wenn das hier unser Automat A ist, und das ist unser Automat A'.
Und wir haben hier irgendeinen Anfangszustand und da irgendeinen
Anfangszustand.
Und hier eine Reihe von Endzuständen.
Naja, dann wollen wir die beiden vereinigen.
Das heißt, wir müssen im Prinzip einen neuen Anfangszustand
konstruieren.
Und von dem aus sowohl darüber laufen können, als auch darüber.
Und dabei wollen wir das gleiche Verhalten erzeugen können wie mit A
oder A'.
Das machen wir auf der nächsten Folie.
Hier ist also noch diese Situation dargestellt.
Wir haben unsere Anfangszustände.
S0 sind grober Fehler.
Hier fehlt der Pfeil, der den Anfangszustand charakterisiert.
Also S0 und S0' sind die Anfangszustände der beiden Automaten A.
Das ist also Automat A, das ist Automat A'.
Jetzt wollen wir einen neuen Anfangszustand dazunehmen, der genau
diese Vereinigung ermöglicht oder das erlaubt, die Vereinigung der
beiden Sprachen zu akzeptieren.
Das heißt, alles das, was Automat A kann, muss auch der neue Automat
können.
Und alles, was Automat A' kann, muss der auch können.
Das heißt doch, wenn ich mir diesen neuen Anfangszustand S02'
anschaue, von dem aus muss ich das gleiche machen können, was der
Automat A macht.
Also alle Übergänge von dem alten Anfangszustand S0 des Automaten A
bleiben erhalten in dem neuen Automaten.
Aber ich füge praktisch die gleichen Übergänge als Übergänge von dem
neuen Anfangszustand S02' hinzu.
Das heißt, wenn ich von S0 mit A auf das SA gehe, dann gehe ich von
S02' mit A auch auf SA.
Ich muss aber auch das Verhalten vom Automaten A' darstellen können.
Das heißt, ich muss von dem S02' mit dem A auch dahin gehen, wo der
Automat A' von S0' aus hingegangen wäre.
Das heißt, ich muss diesen Übergang mit A darstellen und den Übergang.
Und damit habe ich ja genau das, was ich haben wollte.
Ich habe alle Möglichkeiten der Automaten A' erhalten, da habe ich gar
nichts dran verändert.
Ich füge nur einen neuen Anfang hinzu.
Das heißt, das, was ich mache, ist, ich vereinige die Zustandsmengen,
das ist kein Problem, wir sind ja des Jungt.
Ich füge einen neuen Zustand hinzu.
Ich sage, die Endzustände sind gerade die Endzustände des Automaten
A', vereinigt mit den Endzuständen des Automaten A'.
Ich muss eventuell den Zustand S02' auch zu einem Endzustand machen,
falls nämlich das leere Wort von einem der beiden Automaten akzeptiert
wird.
Dann muss das leere Wort auch von dem neuen Automaten akzeptiert
werden.
Das heißt, der Anfangszustand muss gleichzeitig Endzustand sein.
Und dann, wie gesagt, die Übergangsfunktion so, dass wir das Verhalten
von A genau nachbilden.
Das ist genau der Zustand, den Automat A angenommen hätte bei Eingabe
von E im Zustand S.
Und genauso müssen wir das Verhalten von A' nachbilden, wenn das S aus
S' ist.
Und wenn der Zustand gerade der Anfangszustand ist, S02', dann müssen
wir sowohl die Übergänge von S0 abbilden oder einbauen, als auch die
Übergänge von S0', also dem Automaten A'.
Das heißt, der Nichtdeterminismus kommt an dieser einen Stelle nur zum
Tragen, nur von dem neuen Anfangszustand aus haben wir die beiden
Möglichkeiten eingebaut, nichtdeterministisch, und damit haben wir
auch sehr einfache Art und Weise gezeigt.
Wir können also einen nichtdeterministischen Automaten konstruieren,
der offensichtlich jedes Wort aus L von A und auch jedes Wort aus L
von A' akzeptieren kann, weil ja die gleichen Übergänge möglich sind,
und damit sind wir fertig mit dem Beweis, dass eben die Menge der von
endlichen Automaten akzeptierten Sprachen abgeschlossen ist unter
Vereinigung, weil wir diesen Automaten konstruiert haben.
Damit haben wir also diese Konstruktion erledigt, für alle W aus E
-Stern ist es also möglich, von S0 aus jedes Wort zu akzeptieren, das
entweder von A akzeptiert wurde oder von A'.
Und damit haben wir das soweit gezeigt, wie wir das machen wollten und
können uns die nächste Operation angucken.
Also, es gibt andere Operationen, an denen man interessiert ist, zum
Beispiel interessieren wir uns dafür, ist eine Sprache abgeschlossen
unter Produkt?
Was ist ein Produkt?
Also in L mal L' da sind gerade alle Wörter uv drin, sodass U aus L
und V aus L' ist.
Das ist also gerade die Menge aller Konkatenationen, wie man auch
sagt, der Wörter aus L und L'.
Und jetzt ist die Überlegung, wie macht man das?
Also, hier mache ich auch wieder eine disjunkte Vereinigung der
Zustandsmengen.
Also die Idee ist einfach, wenn ich hier meinen Automaten, den einen
Automaten habe, da gehe ich rein mit dem Anfangszustand und habe hier
dann irgendwo Endzustände.
Ich habe hier den anderen Automaten, auch mit dem Anfangszustand und
dann hier irgendwie Endzustände.
Wie mache ich das?
Das ist A, das ist A'.
Die beiden Automaten, die Sprachen L und L' akzeptieren.
Ich muss also zunächst jedes Wort aus L von A akzeptieren können.
Das heißt, ich fange hier ganz normal an.
Das wird also der Anfangszustand unseres Automaten.
Und dann müssen wir, wenn wir hier ein Wort aus L von A akzeptiert
haben im Prinzip, also hier in einem Endzustand sind, dann müssen wir
im Prinzip mit der Eingabe eines Wortes aus L' beginnen können, müssen
das auch akzeptieren können.
Das heißt, normalerweise würden wir im Automaten A' beginnend beim
Anfangszustand auf irgendeinen Folgezustand gehen, wenn wir eine
Eingabe bekommen.
Wir müssen also jetzt von einem Endzustand von A auch zu den
Nachfolgern, zu allen Nachfolgern dieses Anfangszustands von A' gehen
können.
Das hatte ich übrigens in der Folie, die ich verteilt hatte, da fehlte
irgendwie dieser Satz.
Also, von Endzuständen von A zusätzlich alle Übergänge zu Nachfolgern
des Anfangszustands von A'.
Und dann würden wir nach dem Akzeptieren eines Wortes aus L ein Wort
aus L' eingeben und die Eingabe eines Zeichens, also des ersten
Zeichens von V, muss natürlich hier simuliert werden, dadurch, dass
ich von dem Endzustand von A auf den Nachfolgezustand gehe, des
Anfangszustands von A'.
So habe ich hier dann alle Übergänge zu Nachfolgern des
Anfangszustands von A' mit reinzunehmen.
Jetzt müssen wir noch Sonderfälle betrachten, was passiert, wenn
Lambda aus L' ist.
Wenn Lambda aus L' ist, dann heißt das, naja, jedes Wort aus L ist
auch in L mal L' drin, weil ja U mal Lambda gleich U ist.
Das heißt, die Endzustände des Automaten A müssen auch Endzustände
unseres Produktautomaten sein.
Und damit haben wir den Fall dann auch erledigt.
Ich führe das jetzt nicht explizit durch, sondern habe das jetzt nur
so angedeutet, dass man das so machen kann.
Das nächste wäre eine weitere Operation, die Iteration.
Also L' habe ich hier jetzt nicht explizit angegeben, aber ich meine,
ich habe hier noch das aufgeschrieben, habe ich nicht aufgeschrieben.
Also L' Sie wissen, was das ist.
Im Prinzip ist das ein Automat A.
Also hier ist unser Automat A und der hat irgendeinen Anfangszustand
und dann haben wir hier irgendwelche Endzustände.
Jetzt ist die Frage, wir wollen L' akzeptieren.
L' ist ja gerade gleich Vereinigung aller L hoch I über I aus N.
L hoch I, das heißt wir wollen praktisch L beliebig oft mit sich
selbst multiplizieren.
Hatte ich alles zu Anfang der Vorlesung mal dargestellt, wie wir diese
Notationen verwenden.
Also L hoch 0 wäre also das leere Wort oder die Sprache, die das leere
Wort enthält.
L hoch I ist halt gerade L mal L hoch I minus 1.
Das heißt wir machen hier beliebig häufige Produkte von L mit sich
selbst.
Und das heißt, wir müssen, nachdem wir ein Wort aus L eingegeben haben
und vom Anfangszustand gekommen sind auf irgendeinen Endzustand, in
der Lage sein, wieder neu anzufangen mit einem Wort aus A.
Das heißt, wir brauchen von jedem alten Endzustand einen Übergang.
Wir müssen jetzt wieder so tun können, als wenn wir im Anfangszustand
wären.
Also müssen wir jetzt einen Übergang haben auf den Zustand, der
Nachfolger des Anfangszustands ist.
Genauso, wenn hier mehrere halt sind, müssen wir entsprechend auf alle
Nachfolgezustände des Anfangszustands verzweigen können.
Von dem oder den Endzuständen unseres Automaten A.
Und damit haben wir nicht die Terminismus drin, wieder bei diesen
Übergängen, zusätzlich die Möglichkeit bis dort hin zu gehen.
Wir müssen es aber nicht.
Wir können mit dem soweit durchgeführten Produkt schon aufhören.
Das heißt, wir haben die gleichen Endzustände.
Wir haben im Prinzip die gleichen Übergänge.
Wir haben nur diese Iterationsmöglichkeiten von Endzuständen wieder
zurück.
Wir bauen also solche Schleifen ein und können damit beliebige
Wiederholungen von Wörtern aus L auch akzeptieren mit einem nicht
deterministischen Automaten.
Also in jedem Fall bekommen wir hier nicht deterministische Automaten
und wir wissen, dass das die gleiche Mächtigkeit ist wie
deterministische Automaten.
Deswegen haben wir damit dann gezeigt, dass die Menge der Sprachen,
die von endlichen Automaten akzeptiert werden, abgeschlossen sind
unter Vereinigung, Produkt und Iteration.
Warum ist man daran interessiert?
Ich bereite hier gerade etwas vor, was gleich anschließend kommt,
nämlich die Überlegungen, wie man Sprachen charakterisieren kann durch
Operationen.
Sie erinnern sich, dass ich ganz zu Anfang gesagt habe, es gibt drei
verschiedene Arten, Sprachen zu charakterisieren, auf eine generative
Art und Weise oder erzeugende Art und Weise.
Das sind Grammatiken über eine akzeptierende oder analysierende
Methode, das sind die Automaten und eine operationelle Methode.
Darauf werden wir gleich noch kommen und ich habe schon mal gezeigt,
die Sprachen, die von endlichen Automaten akzeptiert werden, sind
abgeschlossen unter Vereinigung, Produkt und Iteration.
Ganz allgemein interessiert uns bei Sprachen auch die Frage, wie
aufwendig ist es eigentlich festzustellen für ein beliebiges Wort über
dem Alphabet, ob das Wort zu der akzeptierten Sprache gehört.
Warum interessiert man sich dafür?
Eine unserer ersten Fragen, die wir gestellt haben zu Anfang dieser
Vorlesung war ja, was ist eigentlich das formale System, mit dem wir
Sprachen beschreiben können, die wir als Programmiersprachen
verwenden.
Ja, was brauchen wir da eigentlich?
Was sind die Strukturen, die wir beschreiben müssen?
Und wenn Sie eine Programmiersprache haben, dann wollen Sie Programme
schreiben und wollen die irgendwie übersetzen lassen, wollen halt
Programme formulieren.
Das heißt, Sie müssen in der Lage sein, zunächst einmal festzustellen,
durch ein entsprechendes Programm, ist überhaupt ein gewisses
Programm, das Sie geschrieben haben, ist das überhaupt ein Wort dieser
Sprache, also ist das entsprechend den Regeln dieser Sprache
formuliert worden?
Oder sind da Fehler drin?
Syntaktische Fehler?
Also die Überprüfung auf syntaktische Korrektheit eines Programms, ist
genau dieses Wortproblem, gehört ein beliebiges Wort über dem
Eingabealphabet, also ein beliebiges von Ihnen geschriebenes Programm,
tatsächlich zu der Programmiersprache, die in der Sie das Programm
schreiben wollten.
Genau das steht hier.
Kann ich, oder wie aufwendig ist es eigentlich, um für ein beliebiges
Wort festzustellen, ist das ein Programm der Sprache Java oder sowas.
Nun ist Java nicht unbedingt eine Sprache, die von endlichen Automaten
akzeptiert werden kann, das wissen Sie, weil wir in Java beliebige
Klammerschachtelungen haben, Klammerschachtelungen sind ja nach
Pumpinglemmer nicht von endlichen Automaten akzeptierbar, aber das
Problem ist eben allgemein das Wortproblem.
Also Wortproblem heißt, wie kann ich die syntaktische Korrektheit
einer beliebigen Zeichenfolge überprüfen, in Bezug auf die Regeln
einer bestimmten Sprache.
Wie aufwendig ist das denn hier bei endlichen Automaten?
Ich muss doch von einem Anfangszustand aus bis zum Endzustand gehen
können.
Ich habe also meinen Automaten hier mit irgendeiner Zustandsmenge.
Der hat hier seinen Lesekopf und ein Band, auf dem unser Wort W steht.
Das muss ich von links nach rechts dieses Wort durchlesen.
In jedem Schritt mache ich einen Übergang, das heißt ich habe für
jedes Zeichen, das ich hier lese, einen Übergang zu machen.
Das ist konstanter Aufwand.
Ich habe eine Tabelle für alle möglichen Übergänge, das ist meine
Übergangsfunktion.
Das heißt, der Aufwand, den ich hier habe, der ist linear in der
Wortlänge.
Für jedes Zeichen nachschauen in der Übergangstabelle, wo muss ich
hinlaufen und dann kann ich weitermachen.
Das ist linear in der Länge.
Groß O von W, die Groß O-Notation kennen Sie, davon gehe ich aus.
Das sollten Sie im Grundlagen Informatik 1 alle gelernt haben.
Groß O vom Betrag von W heißt einfach, dass es im Prinzip nicht
stärker wächst als linear in der Länge dieses Wortes.
Ich habe also eine linear beschränkte Wachstumsfunktion hier.
Und die Konstante ist bestimmt durch den Aufwand, um festzustellen,
was ist der nächste Zustand.
Für nicht deterministische Automaten, wie sieht das da aus?
Da habe ich ja diese Übergänge auf Folgen von Zuständen.
Das ist ja aufwendig.
Also ich habe jetzt von einem Zustand aus eine Menge möglicher
Folgezustände.
Wenn ich mir jetzt den Nachfolgezustand anschaue, habe ich wieder eine
Menge von möglichen.
Ich habe ja diese Verzweigungen, also wenn ich mir das nochmal
aufmale.
Ich habe also von einer Anfangskonfiguration aus ja viele
Möglichkeiten eventuell, zu Folgekonfigurationen zu gehen.
Und jeweils wieder Verzweigungen und wieder Verzweigungen.
Und wir sagten, ein Wort ist akzeptiert, wenn es einen Pfad gibt
dadurch, der zu einem Endzustand führt.
Aber schwierig.
Sie wissen, wie groß Bäume werden können.
Das Wort hat nur endlich viele Zeichen.
Und für jedes Zeichen haben sie einen gewissen Verzweigungsgrad.
Jetzt müssen Sie schauen, gibt es dort einen Pfad, der zu einem
Endzustand führt.
Das riecht nach sehr großem Aufwand.
Aber so groß ist der Aufwand gar nicht.
Denn Sie müssen einfach nur durchlaufen.
Die Größe der Zustandsmenge ist ja beschränkt.
Und Sie können also mit einem Aufwand, der nicht wächst, also der
wächst nur linear mit der Wortlänge.
Und Sie haben hier die Anzahl der Zustände natürlich mit zu beachten.
Sie müssen sich immer merken, was ist die aktuelle Zustandsmenge, in
der ich sein könnte.
Besprechend müssen Sie dort weiterlaufen.
Sie haben aber in jedem Schritt nicht mehr zu tun als einen konstanten
Aufwand, unabhängig von der Länge von W, um die nächste
Folgezustandsmenge zu bestimmen.
Und können nach einer linearen Zeit feststellen, ist in der
Zustandsmenge, die wir erreichen, ein Endzustand enthalten.
Also das, was Sie hier machen müssen mit diesen Zustandsmengen, in
denen Sie jetzt gerade sein könnten, das ist im Prinzip konstanter
Aufwand, unabhängig von der Länge des Wortes.
Nur abhängig von der Anzahl der Zustände des Automaten.
Und das ist eine Konstante.
Also haben Sie hier auch linearen Aufwand, wobei die Konstante hier
etwas größer sein kann, aber es ist auf jeden Fall immer noch linear
an der Wortlänge.
Also linearer Aufwand in der Länge des Wortes, um festzustellen, ob
ein Wort zu der Sprache gehört oder nicht.
Das ist schon mal wichtig.
Und Sie werden sehen, dass wir für Programme das generell hinbekommen,
dass wir einen linearen Überprüfungsaufwand haben für das Wortproblem,
also für die Überprüfung der syntaktischen Korrektheit, wenn wir
geeignete Modelle verwenden.