Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

Nichtdeterministische Endliche Automaten

Name: Nichtdeterministische Endliche Automaten
Uploaded: 2022-11-23T19:17:35+00:00
Duration: 41 min 26 s
Channel: Algorithmen und Datenstrukturen
Description: Der Automat akzeptiert genau die Wörter über \(\{A,O\}\), deren dritter Buchstabe ein \(A\) ist: Die ersten beiden Zeichen sind beliebig, danach muss …

Algorithmen und Datenstrukturen41:26 3.354 Aufrufe veröffentlicht 23. Nov. 2022 Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 237 Zeilen

Herunterladen

Schauen Sie sich mal diesen Automaten hier an. Das Alphabet Sigma besteht aus den beiden Buchstaben A und O. Der Automat hat vier Zustände. Vom Startzustand kommen wir über eine Kante zum
zweiten Zustand. Und an der Kante steht A und O. Das heißt, egal, ob wir einen Buchstaben A oder O lesen, wir kommen vom ersten Zustand in den zweiten. Vom zweiten kommen wir ebenfalls
über eine Kante zum dritten. Da steht auch A und O dran. Also da können wir ebenfalls ein beliebiges Zeichen aus dem Alphabet lesen. Und dann von dem dritten kommen wir in den vierten Zustand. Aber
diesmal nur mit dem A. Wenn da ein O kommt, geht es dort nicht weiter. Dann würden wir den String ablehnen, nicht akzeptieren. Und dieser letzte Zustand hier, in dem wir dann mit dem A gekommen
sind, dieser vierte Zustand ist akzeptieren. Und dort können wir weitere Buchstaben lesen. Egal, ob es A oder O sind, bleiben wir immer in diesem akzeptierenden Endzustand.
Hier ein paar Beispiele von Strings, die der Automat akzeptiert und ein paar Beispiele, die er nicht akzeptiert. Also er akzeptiert zum Beispiel A, A, A oder A, A, A oder O, O, A, O. Oder hier
habe ich noch ein Beispiel A, O, A, O, A, A. Also alle Strings, die als dritten Buchstaben ein A haben, werden von diesem Automaten akzeptiert. Nichts akzeptiert werden Strings, die eben nicht
als dritten Buchstaben ein A haben. Entweder, weil sie gar nicht drei Buchstaben haben, zum Beispiel Epsilon, das leere Wort, hat gar keine Buchstaben, also auch keinen dritten Buchstaben A, wird nicht
akzeptiert. Auch A, A, A, besteht zwar aus As, aber hat nur zwei davon. Kein dritter Buchstabe da, der ebenfalls A wäre, wird also auch nicht akzeptiert. Und A, A, O hat als dritten Buchstaben
O, wird also auch abgelehnt. Hier unten habe ich noch mal ein längeres Beispiel hingeschrieben, wo eben auch der dritte Buchstabe ein O ist. Und die restlichen Buchstaben spielen dann gar keine Rolle
mehr. Da bin ich hier schon im letzten Zustand und bleibe einfach drin. Das Wichtigste ist der dritte Buchstabe, der ist hier entscheidend, um diese Sprache zu definieren. Sobald ich
das einmal verstanden habe, kann ich ziemlich leicht sagen, welche Strings von einem Automaten akzeptiert werden. Ich kann das natürlich hier auch mathematisch hinschreiben. Also die Menge
der akzeptierten Strings, die von diesem Automaten akzeptierten Strings ist die Menge aller W aus Sigma-Sterne, also aller Wörter aus dieser Menge der Strings, die ich aus dem Alphabet Sigma bauen
kann. Und zwar nicht aller Strings W, sondern der Strings, bei dem A der dritte Buchstabe ist. Ja, also so kann man das mathematisch hinschreiben. Ich nenne die Menge zum Beispiel L. L steht für
Language, also Sprache für den Informatiker. Das ist jede Teilmenge von Sigma-Sterne, so was wie eine Sprache. Und das ist also jetzt hier die Sprache, die dieser Automat akzeptiert.
Zu einem Automaten können wir also die entsprechende Sprache bilden. Jetzt können wir das Ganze aber auch mal umgekehrt versuchen. Also wir definieren
zuerst die Sprache und suchen dann nach einem Automaten. Hier zum Beispiel diese Sprache hier. L soll sein W aus Sigma-Sterne. Das gilt A ist drittletzter Buchstabe in W. Also eben war es
der dritte Buchstabe von vorne. Jetzt soll das A der dritte Buchstabe von hinten sein, der drittletzte Buchstabe. Wie sieht denn ein Automat aus, der diese Sprache akzeptiert?
Da könnt ihr jetzt spontan sagen, naja nichts einfacher als das. Ich nehme den Automaten von eben und ändere ihn ein bisschen. Also jetzt geht es nicht darum, dass hier der dritte Buchstabe A
ist, sondern es soll ein Buchstabe A kommen und dann sollen zwei Buchstaben kommen. Die A oder O sein können. Also ich habe wieder vier Zustände. Ich fange hier vorne bei einem Zustand, den habe
ich X genannt, an. Und dann gehe ich mit einem A einen Zustand Y über. Und nach Y kommen jetzt noch zwei weitere Übergänge zu einem dritten und dann am Schluss zum vierten Zustand jeweils mit A und O
bezeichnet. Das heißt, da können jetzt beliebige Buchstaben nach dem A folgen. Und dann ist der letzte Zustand ein akzeptierender Endzustand. Wenn wir das jetzt dabei belassen würden,
würde der Automat nur Strings akzeptieren, die mit A anfangen und dann noch zwei weitere Buchstaben haben. Wir wollen ja aber längere Strings auch akzeptieren. Das heißt, es kann eine
ganze Reihe von Buchstaben kommen und dann soll ein A kommen und dann noch zwei Buchstaben und dann das String aufhören. Das heißt, hier brauchen wir noch einen weiteren Übergang von X auf sich
selbst. Und da kann jetzt beliebige Buchstaben kommen, also A oder O. Ja, prima Automat hat nur ein Problem. Er ist nicht deterministisch. Denn wenn ich hier im Startzustand X bin und
als nächster Buchstabe kommt ein A, dann habe ich ja verschiedene Möglichkeiten, wie ich reagieren kann. Ich kann zum einen diesen Übergang hier nehmen, also von X nach X,
in X also bleiben. Da steht ja ein A dran. Oder ich kann mich dazu entscheiden, jetzt zu sagen, ja, ich nehme den Übergang von X nach Y. Das ist ja auch ein Übergang, an dem A steht. Zwei
Möglichkeiten habe ich. Bei dem Automat ist sozusagen die Übergangsfunktion Delta kaputt. Wenn ich in Zustand X bin und als nächstes ein A kommt, dann steht hier nicht mehr ein Zustand,
sondern es stehen da mehrere Zustände, eine ganze Menge von Zuständen aus Q steht dort. Hier in diesem Fall eben zum Beispiel X und Y. Und genau das war verboten bei deterministischen endlichen
Automaten. Er durfte bei Delta immer nur genau ein Zustand herauskommen. Ist aber schade, könnte man sagen. Warum erlauben wir das denn nicht mal? Und dann könnten wir das doch nicht deterministischen
endlichen Automaten nennen, was dabei herauskommt. Also hier mal die Definition hingeschrieben. Ein nicht deterministischer endlicher Automat, abgekürzt NEA. Ist definiert durch wieder fünf
Dinge, genau wie bei deterministischen endlichen Automaten. Haben wir in einem anderen Video ja schon gesehen. Also erst mal ein Alphabet Sigma, dann eine endliche Zustandsmenge
Q. Dann haben wir einen Startzustand, eine Menge der akzeptierten Endzustände. Das alles noch so, wie es vorher war beim deterministischen endlichen Automaten. Jetzt kommt der einzige Unterschied,
nämlich bei der Übergangsfunktion Delta. Da stand vorher Q Kreuz Sigma auf Q. Das heißt, wir haben immer einen Zustand am Schluss gehabt. Und jetzt steht da nicht mehr Q, sondern P von Q. Und P
steht jetzt dafür, dass es hier eine Teilmenge sein soll. Also wir bilden jedes Paar von aktuellem Zustand und nächsten Buchstaben, die wir lesen, wollen auf eine Teilmenge der Zustandsmenge
ab. Und das ist dann eben die Menge der Zustände, in die wir übergehen können. Dieses geschweifte P steht also für eine Menge, die Teilmengen von Q enthält. Die nennt man Potenzmenge von Q. Hier
steht es nochmal mathematisch hingeschrieben. Die Menge aller S, für die gilt S ist eine Teilmenge von Q. Also die Menge aller Teilmengen von Q, das ist unsere Potenzmenge P.
Durch eine kleine Änderung in der Definition haben wir jetzt also aus dem deterministischen Automaten einen nicht-deterministischen Automaten gemacht. Und der hat jetzt mehr Wahlmöglichkeiten, wie er
von einem Zustand in andere Zustände übergeht. Und da stellt sich natürlich die Frage, wie wirkt sich das denn auf die Menge der akzeptierten Strings aus? Was heißt überhaupt, dass ein String
akzeptiert wird von einem nicht-deterministischen Automaten? Hier haben wir die Definition noch für den deterministischen Automaten. Also ein deterministischer Automat akzeptiert einen
String W, wenn es Zustände gibt, Q0 bis Qn. So das gilt. Am Anfang fangen wir an mit dem Startzustand. Und dann gehen wir, während wir den String lesen, immer zum nächsten Zustand über. Und
am Schluss enden wir dann in einem akzeptierenden Endzustand. Also bildlich hingeschrieben sieht das Ganze so aus. Hier ist der Startzustand, das ist dann das Q0. Dann gehen wir mit W1 in
den ersten Zustand über, mit W2 in den zweiten und so weiter, bis wir am Schluss in dem Zustand Qn sind, wenn wir das letzte Zeichen gelesen haben. Und wenn jetzt hier, wie man an einem
Doppelrand sehen kann, das ein akzeptierende Endzustand ist, dann akzeptieren wir auch den String. Und für den nicht-deterministischen Automaten übernehmen wir genau diese Definition.
Also statt der schreiben wir jetzt näher. Jetzt ist der nicht-deterministische End Automat. Und dann gibt es nur eine Stelle, wo wir hier unten noch was ändern müssen, nämlich an
dieser hier. Jetzt ist das Delta von Qi minus 1,Wi ja nicht mehr ein Zustand, sondern eine Menge von Zuständen. Das heißt, das nächste Qi muss einfach in dieser Menge sein. Sobald Qi aus der Menge der
nächsten Zustände ist, können wir so einen Pfad in unserem Automaten finden. Und wenn es so einen Pfad gibt, dann sagen wir, er akzeptiert den nicht-deterministischen Automaten den String.
Und wenn es so einen Pfad nicht gibt, dann akzeptiert er den String nicht. Ich habe jetzt also definiert, wann ein nicht-deterministischer End Automat einen String akzeptiert, nämlich über
die Existenz eines solchen Pfades hier. Das ist mathematisch gesehen völlig problemlos. Es hat nur einen Nachteil, den wir uns klar machen müssen. Nur weil ein solcher Pfad existiert,
wissen wir noch lange nicht, welcher Pfad es jetzt im Einzelnen ist. Also wir haben zwar gesagt, es muss einen Pfad geben, aber wie wir ihn finden, das sagt die Definition nicht. Warum
das ein Problem sein könnte, können wir uns ganz leicht klar machen an dem Automaten, den wir uns eben schon angestehen haben, also dem nicht-deterministischen Automaten,
der alles Strings akzeptieren soll, bei dem der drittletzte Buchstabe ein A ist. Hier habe ich ein Beispiel für so eine Eingabe. Also W soll sein A-O-A-O-O. Bei diesem String
ist jetzt der drittletzte Buchstabe, also der dritte Buchstabe von hinten ausgezählt. Der ist ein A. Das ist also ein String, den der Automat akzeptieren sollte. Nun stellen wir uns vor, es
geht los. Wir fangen mit dem Startzustand an und als erster Buchstabe kommt ein A. Und jetzt sind wir sofort vor das Problem gestellt, wie geht es denn jetzt weiter? Bleibt er jetzt im Startzustand
oder geht er weiter? An dieser Stelle hat er keine Wahl. Er muss die richtige Entscheidung treffen, um diesen String akzeptieren zu können. Er muss den Übergang vom Startzustand wieder zurück in
den Startzustand nehmen. Denn nur dann kann er nachher einen Pfad finden, der am Schluss im akzeptierenden Endzustand erhält. Also die erste Entscheidung ist, bleibe im Startzustand. Dann
kommt ein O, da hat er nur die Möglichkeit, im Startzustand weiterhin zu bleiben. Und dann kommt das zweite A. Jetzt muss er wieder die richtige Entscheidung treffen. Und die heißt in diesem
Fall, nicht im Startzustand zu bleiben, sondern in den nächsten Zustand überzugehen. Auch da hat er keine Wahl, wenn er mit den letzten beiden Buchstaben, die dann noch kommen, schließlich
den akzeptierenden Endzustand erreichen will. Das heißt, sobald dieses A kommt, was der drittletzte Buchstabe tatsächlich ist, muss er auch dann in den nächsten Zustand übergehen. Und dann kann
er noch weitere Buchstaben lesen, in diesem Fall also zwei Os, um dann am Schluss im akzeptierenden Endzustand zu sein. Und zu sagen, ja, A, O, A, O, O ist tatsächlich ein String, den ich akzeptiere,
ein String, bei dem der drittletzte Buchstabe ein A ist. Wenn wir die Funktionsweise eines nicht deterministischen Automaten also so auffassen wollen, dass sich der Automat, sobald er eine
Wahlmöglichkeit hat zwischen verschiedenen Zielzuständen, also die Übergangsfunktion ihm eine Menge mit mehreren Zielzuständen vorgibt, er eine Entscheidung trifft, welchen von diesen
Zielzuständen er dann in welcher Situation macht, dann müsste der Automat so eine Art mystische Vorhersagefähigkeit haben, die ihm ermöglicht, die richtige Entscheidung an der Stelle zu
treffen. Das heißt, schon jetzt zu wissen, bevor er überhaupt den ganzen String gesehen hat, ob das jetzt der drittletzte Buchstabe ist oder nicht, und dann entsprechend eben die Wahl zu treffen,
was der nächste Zustand sein soll. Und das ist bemerkenswert, denn normalerweise kann ein Endlicher Automat ja nur die Vergangenheit kennen. Also die Buchstaben, die er schon gesehen hat,
die kennt er. Aber was jetzt noch kommen wird und wie viele Buchstaben noch kommen werden, das weiß er ja noch nicht. Und das sehen wir zum Beispiel daran, dass ein deterministischer Automat, der das
gleiche Problem lösen sollte, etwas größer sein muss als so ein nicht deterministischer Automat. Hier, das hier ist der kleinste deterministische Automat, der ebenfalls alle Strings akzeptiert,
bei denen der drittletzte Buchstabe ein A ist und alle anderen Strings verwirft. Und warum ist der so groß? Warum braucht er so viele Zustände? Nun machen wir uns Folgendes klar. Der Automat muss
so funktionieren, dass wenn er einmal ein A liest, also wenn er hier über eine Kante, an der ein A steht, zu einem Zustand kommt, dann muss er dafür sorgen, dass alle Pfade,
die von dort wegführen, nach zwei weiteren Buchstaben in akzeptierenden Endzuständen sind. Das heißt ja genau, wenn ich ein A lese, könnte das ja der drittletzte Buchstabe sein und
wenn es dann noch mit zwei Buchstaben weitergeht, muss danach akzeptiert werden. Wenn es nicht der drittletzte Buchstabe ist, dann geht es natürlich da noch weiter, aber zumindest diese Bedingung
muss erfüllt sein. Nehmen wir mal an, es geht danach noch weiter, dann war das offenbar das A nicht der drittletzte Buchstabe, aber dann kann ja der erste Buchstabe, der danach gekommen sein,
das kann ja auch ein A sein und das kann jetzt der drittletzte Buchstabe sein. Oder der Buchstabe, den ich danach gelesen habe. Und was bedeutet das? Genau, ich muss mir im Grunde die letzten
drei Buchstaben irgendwie merken und da kann dann alle möglichen Kombinationen vorkommen und da der endliche Automat nur eine Möglichkeit hat, Dinge zu speichern, nämlich in seinen Zuständen, braucht
er entsprechend viele Zustände, um immer Bescheid zu wissen, was waren denn die letzten Buchstaben, um dann zu wissen, bin ich akzeptierend oder nicht. In den Zuständen dieses deterministischen
Automaten ist sozusagen die Historie der letzten drei Buchstaben, die der Automat gesehen hat, gespeichert. Diesen Zustand hier hinten zum Beispiel erreichen Sie nur, wenn die letzten drei
Übergänge As gewesen sind. Der speichert sozusagen die Information, die letzten drei Zeichen waren A. Und nur so kommen Sie in diesen Zustand drin und deswegen, wenn Sie hier nochmal ein A lesen,
bleiben Sie natürlich weiter im Zustand. Erst wenn Sie ein O lesen, müssen Sie ihn verlassen, dann sind Sie in diesem Zustand hier und der steht für AAO, also zwei As und dann ein O müssen gewesen
sein und dann ist man in diesem Zustand und der ist eben auch akzeptierend, weil ja der dritte Buchstabe ein A gewesen ist und so weiter. Das gilt für alle anderen Zustände hier auch. Und da
ich mir also drei Buchstaben merken muss, aber für jeden Buchstaben zwei verschiedene Möglichkeiten, A oder O, können die ja sein habe, gibt es insgesamt zwei hoch drei, also acht verschiedene
Kombinationsmöglichkeiten und dementsprechend hat dieser Automat also acht Zustände. Wenn man jetzt also verstanden hat, dass man im Grunde also Buchstabenkombinationen speichern muss und
beim Automaten nichts anderes übrig bleibt zum Speichern als eben mit verschiedenen Zuständen zu arbeiten und auf die Weise wird der Automat natürlich groß, ist es umso bemerkenswerter,
wenn man sich jetzt wieder klarmacht, dass der nicht-deterministische Automat darauf nicht angewiesen ist. Der muss nicht speichern, die letzten Buchstaben, sondern der kann
sich auf seine Fähigkeit verlassen, dass er die Zukunft gucken kann, dass er schon die richtigen vorletzten Buchstaben dann erkennt und dann in den richtigen Moment, wo eben der vorletzte
Buchstabe kommt, dann die Kurve kriegt und in den nächsten Zustand überwechselt, um dann am Ende dann eben akzeptierenden Endzustand zu halten. Der Vorteil von nicht-deterministischen Automaten
liegt bei diesem Beispiel also ziemlich klar vor unseren Augen. Wenn ich auf nicht-determinismus zurückgreifen kann, dann erlaubt es mir eben, viel kleinere und kompaktere Automaten zu bauen,
jedenfalls bei bestimmten Anwendungen, bei dieser Sprache hier, die ist so ein bisschen was wie ein Worst Case für deterministische Automaten, aber eben keine für nicht-deterministische Automaten.
Wenn ich jetzt hier aus dem drittletzten, ein viertletzten, ein fünftletzten Buchstaben usw. mache, dann wird dieser Automat immer nur um einen Zustand länger, während der hier immer
seine Zustandsmenge verdoppeln muss, um sich dann diese längere Geschichte von vergangenen Buchstaben merken zu können. Auf der anderen Seite stellt uns der nicht-deterministische
Automat aber vor das Problem, der eben das gar nicht wissen wollte, wie wir sowas bauen sollen, denn es gibt ja kein elektronisches Bauteil, das uns erlaubt, in die Zukunft zu schauen und zu
wissen, wie wir hier an der richtigen Stelle die richtige Entscheidung treffen sollen. Zum Glück gibt es aber eine Methode, die uns erlaubt, beliebige nicht-deterministische Automaten
in deterministische umzuwandeln. Und wie das geht, das schauen wir uns jetzt als nächstes an. Gehen wir kurz ein Beispiel durch, um uns anzusehen, wie der Automat genau funktioniert.
Also am Anfang sind wir hier in diesem Startzustand, wir markieren ihn grün und dann soll als Eingabe ein A kommen. Und jetzt haben wir eben zwei Möglichkeiten, wie es weitergehen kann. Wir
können hier entweder in dem Zustand bleiben oder wir gehen in den nächsten Zustand über. Das heißt, sobald wir das erste A gelesen haben, haben wir zwei Möglichkeiten, wo der Zustand sein kann. Er
kann sowohl hier im Startzustand sein als auch im nächsten Zustand. Und wir markieren deswegen beide Zustände jetzt hier mit der Farbe grün. Als nächstes wird jetzt ein O gelesen. Und jetzt sehe
ich in Abhängigkeit davon, was ich eben für eine Entscheidung getroffen habe. Also ob ich hier im Startzustand geblieben bin oder in den nächsten Zustand gegangen bin, bin ich jetzt nach dem O in
unterschiedlichen Zuständen. Also wenn ich in den Startzustand geblieben bin und das O kommt, bleibe ich weiterhin im Startzustand. Dann muss ich diese Kante gehen, denn es gibt ja keine andere
Möglichkeit, wie ich mit einem O den Startzustand verlassen kann. Aber wenn ich die Entscheidung eben getroffen habe, bei dem A in den nächsten Zustand zu gehen und jetzt kommt ein O, bin ich
automatisch jetzt also in diesem Zustand hier. Und so sieht dann also die Situation aus, nachdem ich A und O gelesen habe. Und jetzt kommt als nächstes wieder ein A. Und was passiert denn nun?
Ja, jetzt kann ich entweder wieder diese Kante am Startzustand gehen, also wieder hier bleiben im Startzustand. Oder ich nehme hier wieder den Übergang vom Startzustand zum zweiten Zustand.
Und dann gibt es noch eine dritte Möglichkeit. Ich kann ja inzwischen hier in diesem dritten Zustand gewesen sein. Und dann hätte ich mit dem A hier schließlich den Endzustand erreicht. Nachdem
ich A, O, A gelesen habe, kann ich also in drei der vier Zustände sein. Entweder im Startzustand, im zweiten Zustand oder im vierten Zustand. Nur der dritte Zustand ist nicht möglich. Hier habe
ich das jetzt nochmal aufgezeichnet. Wann am Anfang in dieser Kombination möglicher Zustände, nur der Startzustand ist am Anfang möglich. Wenn jetzt der Startzustand, dann kann ich in keinem
anderen Zustand sein. Dann habe ich ein A gelesen, dann waren die ersten beiden Zustände möglich, Zustände in denen ich sein kann. Dann kam ein O, dann war der erste und der dritte Zustand möglich.
Und dann habe ich wieder ein A gelesen und da war der erste, zweite und vierte Zustand möglich. Wie geht es dann weiter, wenn ich hier den nächsten Buchstaben lese? Ja, das ist wieder ein A. Dann
kann ich zum einen hier wieder im Startzustand sein. Also vom Startzustand über diese Kante wieder in den Startzustand gekommen sein. Oder ich bin vom Startzustand in den nächsten,
in den zweiten Zustand übergegangen. Das heißt, der bleibt jetzt ebenfalls grün. Wenn ich jetzt eben im zweiten Zustand war, kann ich jetzt von dort auch in den dritten Zustand übergehen. Das
heißt, jetzt ist der dritte Zustand ebenfalls grün. Und was mit dem vierten Zustand? Ja, wenn ich im vierten Zustand eben gewesen bin nach A, O, A, dann, wenn jetzt noch ein A kommt,
bleibe ich da nicht drin. Dann geht es dort nicht weiter. Dort von dort geht ja keine ausgehende Kante weg. Das heißt, dieser Zustand ist jetzt wieder nicht erreichbar. Das ist also
jetzt die Situation nach A, O, A, A. Erster Zustand ist grün, zweiter Zustand ist grün, dritter ist grün, der vierte ist nicht grün. Das hier unten ist jetzt also der Ablauf,
der sich ergibt, wenn ich die Buchstaben A, O, A, A gelesen habe. Wenn ich andere Buchstaben lese, dann sieht das Ganze anders aus. Stellen wir uns vor, ich habe am Anfang ein A gelesen. Dann
bin ich hier also in dieser Kombination möglicher Zustände. Also ich kann in Zustand 1 und 2 sein, aber nicht in 3 und 4. Und jetzt lese ich ein A. Ja, wie sieht es dann aus? Dann kann ich natürlich
weiterhin im Startzustand sein, wie immer. Ich kann aber auch im zweiten Zustand sein, also durch das zweite A vom Startzustand in den zweiten Zustand übergegangen sein.
Ich kann jetzt aber auch vom zweiten Zustand, in dem ich ja durch das erste A gekommen sein kann, auch in den dritten Zustand übergegangen sein. Nur den vierten Zustand, da kann ich
noch nicht drin sein. Das heißt, erreichbare Zustände an der Stelle sind die Zustände 1, 2 und 3. Und genau die Kombination habe ich hier schon hingeschrieben. Das heißt, jetzt könnte
ich von hier aus sozusagen einen Übergang nach hier hinten zeichnen und da ein A dranschreiben. Sie sehen, worauf das hinausläuft. Hier unten bin ich gerade dabei, schon einen neuen Automaten zu
bauen, also genau den, den ich haben will, nämlich einen deterministischen Automaten, der dieselbe Sprache akzeptiert wie der Automat hier oben. Und der Automat hier unten hat aber
eine andere Art von Zuständen als der hier oben. Beim nicht deterministischen Automaten waren die einzelnen Kreise die Zustände. Da gab es dann vier verschiedene Zustände und die konnten
erreicht werden oder auch nicht, je nachdem, was hier von einer Eingabe kommt. Hier unten habe ich jetzt pro Zustand vier Kreise. Also jeder Zustand des Automaten hier unten entspricht einer
Kombination von Zuständen hier oben beim nicht deterministischen Automaten, nämlich der Zustand, die hier grün eingezeichnet sind, also der erreichbaren Zustände. Jeder Zustand des neuen
deterministischen Automaten entspricht also einer Kombination möglicher erreichbarer Zustände des ursprünglichen nicht deterministischen Automaten. Wenn wir das Spiegel jetzt weitertreiben, kommen
wir am Ende hier an. Und wir sehen, das ist ja von der Struktur genau der gleiche Automat, den wir eben schon gesehen haben. Der deterministische, endliche Automat, der die Sprache akzeptiert,
die alle Wörter enthält, bei denen der drittletzte Buchstabe ein A ist. Nur diesmal sind die Zustände anders dargestellt. Die einzelnen Zustände dieses deterministischen, endlichen Automaten
entsprechen jeweils Kombinationen von Zuständen, die erreicht werden können, indem nicht deterministischen Automaten, den wir oben gesehen haben, den mit den vier Zuständen,
also alle Kombinationen, die überhaupt möglich sind, sind hier aufgezählt. Und das sind eben acht Stück, denn der erste Zustand ist ja immer erreichbar. In dem Stadtzustand können wir hier
immer sein. Und nur die anderen Zustände sind entweder mögliche aktuelle Zustände oder auch nicht. Je nachdem, was für Buchstaben wir gelesen haben, bleiben also zwei, drei,
acht mögliche Zustandskombinationen in die, der nicht deterministischer, endlicher Automat gewesen sein kann. Und hier in diesem Automat sehen wir sie alle. Ja, jede dieser Kombinationen ist ein
Zustand dieses Automaten und die Kanten dazwischen sind eben die Übergänge von einer Kombination in die andere. Insgesamt also ein deterministischer Automat. Was ist jetzt der Startzustand von diesem
Automaten? Ja, genau dieser Zustand hier, an den der schwarze Pfeil gemalt ist, das ist der Zustand, in den auch der nicht deterministische Automat startet. Also nur der Startzustand des
nicht deterministischen Automaten ist grün. Alle anderen Zustände sind weiß. Und diese Kombination ergibt jetzt den Startzustand unseres deterministischen Automaten hier. Und was sind
jetzt die Endzustände dieses Automaten? Ja, alle Zustände, in denen der entsprechende Endzustand des nicht deterministischen Automaten erreichbar gewesen wäre. Also überall, wo hier dieser letzte
Kreis grün ist, das sind genau die Endzustände dieses deterministischen Automaten hier. Hier spiegelt sich die Definition wieder, wann ein nicht deterministischer endliche
Automat einen String akzeptiert. Nämlich genau dann, wenn es einen Pfad gibt, der die Buchstaben des Strings liest und am Ende in einem akzeptierenden Endzustand endet. Das heißt,
sobald ich hier die Möglichkeit habe, in einem akzeptierenden Endzustand zu sein, ist das für den nicht deterministischen Automaten ein akzeptabler String. Deswegen müssen wir bei dem Automaten,
der die Kombination aller möglichen Zustände enthält, auch diese ganzen Zustände hier umkreisen und zu akzeptierenden Endzuständen des Automaten hier machen. Wir haben jetzt hier also einen Weg
gesehen, wie man aus deterministischen Automaten einen entsprechenden nicht deterministischen Automaten erzeugen kann, der dieselbe Sprache akzeptiert. Und zwar, indem wir sozusagen alle
Wege, die hier im nicht deterministischen Automaten gegangen werden können, weil man Wahlmöglichkeiten hat, welche Übergänge man nimmt, alle diese Wege parallel durchführt bzw.
nicht die Wege parallel nimmt, sondern immer sich merkt, in welchen Zuständen diese Wege, alle Wege, die möglich sind, denn enden können. Und diese Zustandsmengen, in denen wir dann
gerade sein können, die bilden dann gerade die Zustände des deterministischen Automaten. Durch die Erfindung von Nicht-Determinismus habe ich jetzt also zwar dafür gesorgt,
dass Automaten vielleicht ein bisschen kleiner und kompakter dastehen können, aber ich habe es nicht geschafft, neue Entscheidungsprobleme zu lösen, weil für jeden nicht deterministischen
Automaten kann ich einen entsprechenden deterministischen Automaten konstruieren. Wo ich also gerade schon dabei war, mir zu überlegen, was könnte denn Automaten noch
können und wurde dadurch mächtiger, also kann er mehr Entscheidungsprobleme lösen, habe ich hier noch einen weiteren Vorschlag, was wir denn dem Automaten noch ermöglichen können. Bisher ist
es ja so, dass bei jedem Übergang ein Buchstabe gelesen wird. Und das heißt, wenn ich N Buchstaben als Eingabe habe, bin ich nach N Übergängen auf jeden Fall fertig. Ja, denn jeder Übergang liest
ja genau einen Buchstaben. Manchmal will ich das aber vielleicht nicht. Manchmal ist es vielleicht günstig zu sagen, ja, du könntest jetzt hier einen Übergang machen und dabei gar keinen
Buchstaben lesen. Und so einen Übergang nennen wir Epsilon-Übergang. Epsilon ist das Symbol für den Leerstring, also den String der Länge 0, der gar kein Zeichen beinhaltet. Und ich erweitere jetzt
mein Konzept für Automaten durch eine neue Art von Kanten. Das sind hier diese grünen Kanten, die jetzt das Epsilon als Markierung haben. Und das sind jetzt die Epsilon-Übergänge. Das heißt,
sie erlauben einen Übergang von einem Zustand in einen anderen Zustand, ohne dass ein Zeichen gelesen wird. Ich könnte in diesem Beispiel Automaten vom Startzustand, ohne
ein Zeichen zu lesen, in diesen akzeptierenden Endzustand überwechseln. Denn hier ist ja ein Epsilon-Übergang. Und das nicht genug. Ich könnte auch weiter ohne wiederum ein Zeichen zu lesen,
auch in diesen dritten Zustand hier übergehen. Denn hier gibt es ja noch einen Epsilon-Zugang von dem Endzustand in diesen dritten Zustand hier. Obwohl bei diesem Automaten
der Startzustand nicht akzeptierend ist, akzeptiert er also das leere Wort, weil er eben die Möglichkeit hat, ohne etwas zu lesen, in einen akzeptierenden Endzustand überzugehen.
Jetzt müssen wir die Definition wieder anpassen. Also ein nicht deterministischer Endsticherautomat mit Epsilon-Übergängen, ein Epsilon-Näher, ist definiert durch wieder fünf Dinge. Und die
ersten vier sind genau wie vorher. Also Alphabet, Zustandsmenge, Startzustand, Endzustandsmenge, genau wie beim deterministischen oder beim nicht deterministischen Automaten. Erst bei
der Übergangsfunktion ergibt sich jetzt wieder eine Neuerung. Jetzt haben wir hier ein Delta, das von Q Kreuz und jetzt wird das Sigma um dieses Zeichen Epsilon erweitert. Das Epsilon ist kein
Buchstabe. Also das Epsilon war noch nicht in dem Signal drin. Das Epsilon ist ein Zeichen, was einfach für diesen Leerstring steht und was die Epsilon-Übergänge markiert.
Also Sigma vereinigt mit Epsilon ist jetzt sozusagen das Neue, was wir hier in diese Übergangsfunktionen rein geben können. Und das Ziel ist wieder, außer Potenzmenge von Q, es
ist ein nicht deterministischer Endlicherautomat mit Epsilon-Übergängen. Was bedeutet es jetzt, wenn ich hier an der zweiten Stelle statt eines Buchstabens das Epsilon einsetze? Ja,
da steht hier Delta von Q, Epsilon ist die Menge der Zustände, von denen ich, wenn ich in Q bin, gelangen kann, ohne dass ich überhaupt ein Zeichen von der Eingabe lesen muss.
Jetzt muss ich wiederum definieren, wann genau akzeptiert denn ein Epsilon näher einen Eingabe-String W? Und dazu brauche ich jetzt hier kurz noch folgenden Begriff, nämlich den des
Epsilon-Pfades. Also ein Epsilon-Pfad von einem Zustand X zu einem Zustand Y ist eine Kette von Epsilon-Übergängen, die mich von X zu Y bringen. Also hier ist nochmal formal hingeschrieben,
ich habe hier ein Q1, Q2, Q3 bis Qn. Und das Q1 ist gleich dem X und das Qn ist gleich dem Y. Und ich habe immer einen Epsilon-Übergang von dem Qi-1 auf das Qi. Gezeichnet sieht es also so aus,
vom Zustand X gibt es hier eine Kette von Epsilon-Übergängen, die mich am Schluss nach Y führen. Und das könnte ich zum Beispiel auch so zeichnen. Das ist jetzt kein einzelner Übergang,
sondern das ist eben die Kette von Übergängen. Das kennzeichne ich hier mit dem kleinen Stern. Also von dem X komme ich jetzt hier über eine beliebige Anzahl von Epsilon-Übergängen nach Y. Und
allgemein könnte ich auch sagen, es reichen auch 0 Epsilon-Übergänge aus. Wenn nämlich X gleich Y ist, dann wäre das ein Epsilon-Pfad der Länge 0. So definieren wir das jetzt hier auch mal.
Mit diesem Begriff des Epsilon-Pfades können wir uns jetzt an die Definition wagen, wann denn ein Epsilon näher einen String W aus Sigma-Stern akzeptiert. Nämlich genau dann,
wenn es Zustände Q1,Q1-, Q2,Q2- und so weiter bis Qn,Qn- aus der Zustandsmenge Q gibt. Wir haben also jetzt für jeden Buchstaben W i aus dem Eingabe-String zwei Zustände
Q i und Q i- aus der Menge der Zustände Q. Und die Idee ist die, da sehen wir hier unter Punkt 2, ganz einfach, wenn ich das Zeichen W i lese, dann gehe ich von dem Zustand
Q i in den Zustand Q i- über. Und dann muss ich natürlich weiter zum nächsten Zustand Q i plus 1. Und das ist genau hier bei Punkt 3 gesagt. Also es gibt einen Epsilon-Pfad von
Q i- nach Q i plus 1. Und jetzt muss ich natürlich noch dafür sorgen, dass mit dem Startzustand losgeht. Das heißt, ich habe einen Epsilon-Pfad von S nach Q 1. Und dann muss ich dafür sorgen,
dass ich am Schluss auch in einem akzeptierenden Endzustand lande. Das heißt, dann muss es einen Epsilon-Pfad von dem Qn-Zustand, also dem Zustand, den ich erreiche, wenn ich das
letzte Zeichen W n gelesen habe, zu einem Zustand aus der akzeptierenden Endzustandsmenge F geben. Das Ganze jetzt nochmal übersichtlicher grafisch dargestellt. Also es muss eine Kette von Zuständen
geben. Und wir fangen an natürlich mit dem Startzustand S. Und von dort gibt es dann einen Epsilon-Pfad zum Zustand 1. Das ist der Zustand Q 1, in dem wir dann das erste Zeichen lesen und
den Zustand 1-String erreichen. Von dort gibt es dann einen Epsilon-Pfad zum Zustand 2. Dort lesen wir das W 2 und sind dann im 2-String und dann so weiter, bis wir am Schluss im Zustand
Q n sind. Und dort lesen wir dann den letzten Buchstaben n, sind dann im Zustand Q n-String. Und von dort gibt es dann einen Epsilon-Pfad bis zu einem akzeptierenden Endzustand. Und denken
Sie dabei daran, diese Epsilon-Pfade können auch die Länge 0 haben. Das heißt, es kann auch sein, dass der Q 1 gleich dem S ist. Dass da einfach gar keine Übergänge stattfinden müssen,
weil ich direkt in dem Startzustand Q 1 bin. Und auch hier überall anders, wo Epsilon-Stern steht, kann auch einfach die beiden Knoten identisch sein. Und dann lese ich eben ein Zeichen und
direkt danach das nächste Zeichen. Machen wir hier kurz ein Beispiel. Das soll hier das Wort sein, was ich mit dem Automaten hier verarbeiten will. A, a, a, o, a, o. Da kommt kein Epsilon drin vor.
Also Vorsicht, das Epsilon ist nur ein Symbol dafür, dass ich kein Zeichen lesen muss. Das ist kein Buchstabe aus meinem Alphabet. Ich fange also mit dem Startzustand hier an und habe dann gleich
die Entscheidung, was mache ich denn? Es ist ein nicht-deterministischer Automat. Ich kann jetzt zum einen hier entlang laufen, zu diesem Knoten gehen und das A lesen. Ich könnte aber auch hier
den Epsilon-Übergang machen und den zweiten Epsilon-Übergang. Und dann habe ich hier auch eine Kante, an der a steht. Und dann könnte ich dort ebenfalls das a lesen. Ich entscheide mich
jetzt mal dafür, hier runter zu gehen. Da habe ich das erste a gelesen und dann lese ich das zweite a. Dann bin ich wieder hier oben. Also nach a, a bin ich wieder am Startzustand. Und jetzt kommt
ein drittes a. Und da entscheide ich mich jetzt einfach mal, den Epsilon-Übergang zu nehmen und hier ebenfalls einen anderen Epsilon-Übergang zu nehmen. Und dann bin ich in diesem Zustand
hier oben. Und von dem aus nehme ich jetzt den Weg hier unten hin und habe also das dritte a gelesen. Und jetzt habe ich den Vorteil, dass ich das gemacht habe, dass ich nämlich jetzt ein
o lesen kann. Das kommt als nächster Buchstabe. Jetzt lese ich das o. Und nun kommt hier nochmal ein a. Und jetzt hätte ich wieder die Möglichkeit, über den Epsilon-Übergang hier oben hinzugehen,
das a zu lesen. Diesmal kann ich aber zum Beispiel auch hier lang gehen. Da gibt es ja direkt eine Kante zu diesem Knoten hier, die mit a beschriftet ist. Dann habe ich das letzte a gelesen. Und
jetzt kommt am Schluss noch ein o. Und das führt mich wieder zurück zum akzeptierenden Endzustand. Das heißt a a o a o wird von diesem Automaten mit Epsilon-Übergang akzeptiert.
Mit der Einführung von Epsilon-Übergang kann der endliche Automat jetzt etwas, was er vorher noch nicht konnte, nämlich abstürzen. Super! Das kennen wir von Computern ja auch schon,
dass sie immer weiter laufen und niemals zum Ende kommen. Das haben wir jetzt dem Automaten auch ermöglicht. Und zwar dann, wenn es im Automat einen solchen Zyklus von
Epsilon-Übergängen gibt. Sehen wir hier als Beispiel. Also wir können hier anfangen am Stadtzustand an ein a lesen und dann sind wir im Zustand x. Wenn wir dann in Zustand x sind,
können wir einen Epsilon-Übergang zum Zustand y nehmen. Und von dem gibt es dann wieder einen Epsilon-Zugang zum Zustand x. Das heißt, wir können hier immer hin und her wechseln x, y, x,
y, x, y, y, ohne jemals die Eingabe weiterzulesen, ohne jemals zu einer Entscheidung zu kommen, ob wir jetzt die Eingabe akzeptieren wollen oder nicht. Das heißt, bei so einem Automaten
können wir beliebig lange Pfade anführen, die dann einen String akzeptieren oder auch nicht akzeptieren. Das ist nur kein großes Problem, weil wir solche Epsilon-Zyklen auch einfach
vermeiden können. Wir können sie wegnehmen. Denn in dem Moment, in dem wir von x nach y kommen und von y wieder nach x, gibt es gar keinen Grund zwischen x und y zu unterscheiden. Das heißt,
ich kann genau beide Knoten auch zusammensetzen, hier einen Knoten x, y daraus machen. Der ist dann auch akzeptierend, weil y akzeptierend war. Also sobald wir zwei Knoten miteinander verschmelzen
und einer ist davon akzeptierend, wird der verschmolzene Knoten ebenfalls ein akzeptierender Endzustand. Und dann haben wir diesen Automaten hier erreicht, wo dann kein Epsilon-Zyklus mehr
enthalten ist. Und der akzeptiert genau die gleiche Sprache wie der Automat hier oben. Weil Epsilon-Zyklen kein großes Problem sein können, erkennt man auch daran, dass man
einen Automaten mit Epsilon-Übergängen in einen deterministischen Automaten ohne Epsilon-Übergänge verwandeln kann. Und zwar mit genau der gleichen Methode, die wir uns eben schon bei den nicht
deterministischen Automaten angeschaut haben. Wir protokollieren einfach immer mit, welche Zustände denn in welcher Situation erreichbar sind in dem Automaten und machen dann aus dieser Zustandsmenge
einen Zustand für den deterministischen Automaten, den wir dann damit aufbauen. Schauen wir uns nochmal unseren Automaten an. Also hier ist der Startzustand und den kann ich dann also,
wenn ich beginne, erreichen. Aber das ist nicht alles. Ich kann auch gleich beim Starten von diesem Startzustand ja in diesen Endzustand übergehen. Das heißt, direkt am Anfang
ist auch dieser Zustand erreichbar. Dabei eben über einen Epsilon-Übergang und dann über zwei Epsilon-Übergänge kann ich auch diesen dritten Zustand hier erreichen. Das heißt, am Start sind
das die drei zugänglichen Zustände. Und deswegen werde ich hier jetzt in meinem kleinen Zustand für den deterministischen Automaten auch diese ersten drei Zustände hier alle grün einzeichnen. Jetzt
kann ich ein A oder ein O lesen. Fangen wir mal mit dem A an. Wenn die Situation so ist wie hier, kann ich von dem Startzustand über das A in diesen Zustand wechseln. Das heißt, dieser
Zustand hier unten wird grün. Der Startzustand ist aber nicht mehr grün. Nach dem ersten A, was ich gelesen habe, kann ich dort nicht mehr drin sein. Das heißt, der ist jetzt nicht mehr grün.
Ist der noch grün? Ja, auch nicht mehr. Ich kann zwar von hier in den Zustand übergegangen sein, aber ich kann nach dem A nicht mehr in diesem akzeptierenden Endzustand sein. Nur ein einzelnes
A wird von dem Automaten nicht akzeptiert. Und hier ebenfalls, von hier kann ich ebenfalls hier runtergegangen sein. Das heißt, jetzt sieht die Situation insgesamt so aus. Was passiert jetzt,
wenn ich wieder ein A lese? Dann wird das Ganze umgedreht. Von dem Zustand hier komme ich ja über ein A wieder zum Startzustand. Von diesem Zustand hier komme ich über ein A nirgendwo hin. Das
heißt, der wird jetzt einfach entfernt. Der ist jetzt frei. Sieht jetzt so aus. Nein, ich kann ja vom Startzustand wieder mit Epsilon übergehen, zu den beiden hier übergehen. Das heißt, jetzt kriege
ich wieder diesen hier und auch diesen Zustand in meine erreichbare Zustandsliste. Das heißt, ich kann von hier unten wieder über ein A zu dem Zustand hier oben zurückwechseln.
Und was ist, wenn ich jetzt in der Situation bin und ein O lese? Ja, hier links entfallen jetzt die Zustände. Ich muss jetzt im rechten Teil des Automaten sein, denn nun hier kommen die Os vor.
Das heißt, dieses Grün vom Startzustand fällt schon mal weg. Hier drüben gibt es aber durchaus Möglichkeiten, ein O zu lesen, nämlich wenn ich in diesem Zustand bin und dann das O lese und
dann komme ich in den Zustand hier oben. In den Endzustand selbst kann ich aber nicht bleiben, wenn ich ein O lese. Das heißt, das ist hier die Zustandsmenge, die ich erreichen kann,
wenn ich im Startzustand bin und dann ein O gelesen habe. Und wenn wir das jetzt weiterführen, kommen wir am Ende bei diesem Automaten hier unten an. Es gibt nur sechs verschiedene
Kombinationen von Zuständen des ursprünglichen Epsilon-Neas, die wir in Betracht ziehen müssen. Alle anderen Kombinationsmöglichkeiten, die man denken könnte, die auch vorkommen könnte,
kommen einfach nicht vor, sind nicht erreichbar. Es bleiben nur sechs übrig. Das heißt, dieser Dea hier unten hat nur einen Zustand mehr als der ursprüngliche Epsilon-Nea, den wir hier oben
verwendet haben, akzeptiert aber dieselbe Sprache und aber ist er deterministisch. Das heißt, von jedem Knoten dieses Dea aus gibt es immer eine Kante mit O und eine Kante mit A und nicht mehrere
und auch kein Epsilon natürlich. Die Epsilons sind wir auf diese Weise auch noch losgeworden. Und das ist noch nicht alles. Schauen Sie sich diesen Zustand hier an. Da ist ja gar nichts grün,
also kein Kreis ist grün markiert. Das heißt, alle Zustände im ursprünglichen Epsilon-Nea waren nicht erreichbar. Und wie kann das passieren? Ja, genau dann, wenn unsere Übergangsfunktion nicht
total definiert ist. Wenn wir hier zum Beispiel zuerst ein O lesen, dann müssen wir hier in diesem Zustand sein. Wenn dann noch ein O kommt, gibt es hier keine Kante mit einem O. Das heißt, danach
ist die Zustandsmenge, die erreichbar ist, leer. Das heißt, dies hier ist nichts anderes als der Müllzustand, über den wir schon einmal bei anderer Gelegenheit gesprochen haben. Also der Zustand,
in den ich überwechseln kann, wenn ich weiß, ich akzeptiere den String sowieso nicht, egal was noch kommt. Dann sieht man hier, sobald ich in diesem Zustand bin, kann ich mit allen Buchstaben
A und O, die kommen würden, wieder zurückgehen in diesen Zustand. Das ist der Müllzustand und den kann ich genauso gut weglassen, hatten wir ja gesagt. Wir haben ja definiert,
dass wenn es keine Übergänge gibt, dann eben der Automat anhält und die Eingabe verwirft. Und dann habe ich tatsächlich bei meinem deterministischen endliche Automat auch nur fünf Zustände, genauso
wie beim ursprünglichen nicht deterministischen Automaten mit Epsilon-Übergängen. Die zusätzliche Möglichkeit für nicht-deterministische Übergänge oder sogar für Epsilon-Übergänge muss also nicht
zwangsläufig dazu führen, dass die Automaten kleiner werden, sondern es kann bei vielen Problemen auch einfach sein, dass wenn wir einen Epsilon näher oder einen Näher haben,
ein entsprechender Dea, also ein deterministischer endliche Automat, der dieselbe Sprache akzeptiert, tatsächlich die ähnliche Größe oder eine sehr vergleichbare Größe hat. Es gibt aber auch andere
Fälle, wo das nicht so ist. Und ein Beispiel dafür hatten wir vorhin ja gesehen. Wenn wir also sagen, der K letzte Buchstabe eines Strings muss A sein zum Beispiel, dann brauche ich, wenn ich
das mit deterministischen Automaten machen will, zwei hoch-K verschiedene Zustände. Ich brauche aber nur K plus einen Zustand, wenn ich das mit einem nicht-deterministischen Automaten machen
will. Das heißt, es gibt Worst-Case-Beispiele, wo diese Möglichkeiten mit Nicht-determinismus und vielleicht sogar mit Epsilon-Übergängen umzugehen tatsächlich was bringt. Nicht-determinismus
und Epsilon-Übergänge können also schon recht nützlich sein. Sie sorgen dafür, dass wir mehr Möglichkeiten haben, Automaten kompakt darzustellen. Und manchmal sind sie
deutlich kompakter als die entsprechenden deterministischen Automaten. Auf der anderen Seite bringen diese neuen Möglichkeiten nichts in Bezug auf die Entscheidungsprobleme, die ich mit
Automaten lösen kann. Wenn ich zum Beispiel einen deterministischen Automaten habe, dann kann ich den natürlich auch als nicht-deterministischen Automaten und sogar als Epsilon-Näher
auffassen. Ich muss ja die Möglichkeiten nicht verwenden. Das Umgekehrte gilt aber auch, sobald ich zu einer Sprache einen Epsilon-Näher habe, der diese Sprache akzeptiert, kann ich genauso
gut auch einen Dea bauen, der dieselbe Sprache akzeptiert. Der hat vielleicht ein paar Zustände mehr, aber er kann dieselbe Sprache akzeptieren. Das heißt, alle Entscheidungsprobleme, die ich mit
Epsilon-Näher lösen kann, kann ich auch mit Dea lösen. Und dasselbe gilt natürlich auch für Nea, wenn ich keine Epsilon-Übergänge habe. Das heißt, alle drei Maschinenmodelle,
die wir uns hier angeschaut haben, sind in Wahrheit gleich mächtig. Sie können alle die gleiche Menge von Entscheidungsproblemen lösen. Um das Maschinenmodell tatsächlich mächtiger zu
machen, reicht es also nicht aus, einfach nicht-determinismus- oder Epsilon-Übergänge einzuführen. Da müssen wir mehr tun und das werden wir in einem späteren Video machen. Da
werden wir dem Automaten noch einen zusätzlichen Speicher geben. Und sobald er diesen Speicher hat, kann der Automat dann zusammen mit dem Speicher mehr machen, als wenn er den Speicher nicht hätte.

Zum Nachlesen

Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den … Eindeutiger endlicher AutomatDer eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl. PotenzautomatEin endlicher Automat A heißt Potenzautomat des endlichen Automaten B, wenn seine Zustandsmenge gerade die Potenzmenge der Zustandsmenge von B ist. Formal … Automat (Informatik)Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.