Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Regulären Ausdruck in NEA umwandeln - Automaten und Formale Sprachen 7
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 54 Zeilen
- Moin Leute, Ihr wisst bescheid über die Automaten, ihr wisst bescheid über reguläre Ausdrücke… Dann können wir das jetzt connecten.
- Heute ziehen wir uns mal rein, wie man aus nem Regulären Ausdruck ein NEA basteln kann. uuuund bitte!
- Also jut! Wir wir ja schon gelernt haben existiert zu jedem regulären Ausdruck ein endlicher Automat.
- Wir konstruieren dazu den nichtdeterministischen endlichen Automaten. Abgekürzt den NEA.
- Aber nicht irgendein NEA sondern den mit Epsilon Übergängen, also den Epsilon NEA. Was war an dem nochmal so besonders?
- Ah jo mit dem dürfen wir einfach so yolonese mäßig in ein anderen Zustand jumpen ohne ein Zeichen zu lesen.
- Nice! Zurück zum Thema: Vom Prinzip funktioniert dat ganze so: Wir
- bekommen einen Ausdruck , diesen zerlegen wir dann in Teilausdrücke und daraus konstruiere ma dann den Automate.
- Isch easy! Damit ma das mache könne, gibt’s bestimmte Konstruktionsregeln.
- Die schauen wir uns jetzt mal an: Als aller erstes gehen wir mal die sogenannten Basisfälle durch: Haben wir einen Ausdruck der einfach eine
- leere Menge enthält, würde das ganze so aussehen: Wir haben ein Anfangszustand und einen Endzustand.
- Allerdings passiert eigentlich rein gar nix. Naja macht ja auch Sinn, in der leeren Menge steht ja auch nischt drin.
- Der nächste Basisfall betrifft das leere Wort: Hier erzeugen wir ein Anfangszustand, einen Endzustand und verbinden das mit der Epsilon
- Kante. Also dem Pfeil und so, weißte?
- Der dritte Basisfall ist ähnlich wie das leere Wort. Hier haben wir aber ein Symbol oder Wert aus dem Alphabet, zum Beispiel a.
- Wieder erzeugen wir ein Anfangszustand und einen Endzustand und verbinden den ganz normal mit dem Wert den wir bekommen.
- Verbindungen von Ausdrücken Okay soweit so gut! Was passiert, wenn wir Ausdrücke haben wie diese hier:
- Logisch dafür gibt es auch Regeln. Wie überall.
- RS oder auch R mal S ist die Verkettung. Damit hier das Wort akzeptiert werden kann, wird erst der Ausdruck R vom Anfangszustand
- bis zu seinem Endzustand durchlaufen. Danach gehen wir mit Epsilon in den Anfangszustand vom zweiten Ausdruck S und durchlaufen den
- bis zum Ende. Einfach gesagt wir verbinden beide Ausdrücke mit dem Epsilon Übergang.
- Klar oder? Jut dann gehen wir mal die anderen Fälle durch.
- Was ist wenn wir eine Alternative haben. Sprich R+S.
- Da es ja Alternative heißt müssen wir die Ausdrücke auch aufteilen. Das heißt wir beginnen mit einem Anfangszustand.
- Von dem wechseln wir mit Epsilon entweder in den Ausdruck R oder in den Ausdruck S. Die Ausdrücke gehen wir dann ganz normal wieder durch und wechseln dann wieder mit
- Epsilon zum Endzustand. Keine Angst wir schauen uns dazu noch ein Beispiel an.
- Aber vorher schauen wir uns noch die Regel zur Kleenschen Hülle an. Haben wir ein Ausdruck mit so nem Stern dahinter machen wir folgendes:
- Wir starten ganz normal in einem Anfangszustand. Gehen dann mit Epsilon in den Ausdruck.
- Und durchlaufen diesen. Anschließend gelangen wir wieder mit Epsilon in den Endzustand.
- Innerhalb des Ausdrucks können wir zurückspringen damit wir ihn beliebig oft wiederholen können. Den Anfangszustand verbinden wir auch gleich noch mit dem Endzustand, damit wir auch das
- leere Wort akzeptieren können. Holla die Waldfee!
- Was könnt ihr euch merken: Um aus einem regulären Ausdruck eine Epsilon NEA zu bauen, muss man gewisse Regeln anwenden.
- Beispiel Von Ausdruck zu NEA Machen wir gleich mal ein Beispiel, damit es klarer wird.
- Sagen wir mal so nen frehser Dude will aus diesem Ausdruck nen Automaten konstruieren: (a+b)*ab Wir
- haben einmal a+b, das ganze dann in der Kleenschen Hülle und das verkettet mit ab.
- Fangen wir mal mit a+b an. Den Ausdruck a können wir ja ganz einfach mit dem Basisfall hinschreiben
- Sprich Zustand verknüpft mit a zum Endzustand. Jetzt fügen wir das + bzw. oder ein: Wir starten im Anfangszustand und können
- mit Epsilon in a wechseln oder in den zweiten Ausdruck. Der zweite Ausdruck wäre dann einfach b.
- Joa geil. Als nächstes fügen wir den Kleenschen Stern hinzu.
- Der bezieht sich dabei auf den gesamten Ausdruck a+b. Also fügen wir erst vorne einen neuen Anfangszustand ein und am Ende auch einen neuen Endzustand.
- Die verbinden wir jetzt mit dem Epsilon Übergang. Jetzt müssen wir nur die Wiederholung einfügen.
- Sprich wir verbinden den alten Endzustand mit dem alten Anfangszustand von a+b. Und simsalabim wir können a+b so oft wiederholen, wie wir Stifte zum schreiben haben.
- Zum Schluss kommt noch der letzte Tei dazu: ab Da wir das ganze ja mit der Verkettung bzw. dem UND verbinden, müssen wir einfach nur
- a und b mit den entsprechenden Bopeln an den alten Endzustand dranhängen. Damit sind wir durch und haben unsern Automaten konstruiert.
- Was kann man sich merken: Um aus einem regulären Ausdruck einen Automaten zu konstruieren.
- Zerlegen wir zunächst den Ausdruck in Teilausdrücke und wenden darauf die Regeln an. Die Regeln muss man leider wissen, am Besten ihr schreibt sie euch irgendwo auf oder schaut
- auf unsere Lernplattform da ist auch alles zu finden. Probiert selbst mal aus einem Ausdruck ein NEA mit den gegebenen Regeln zu konstruieren.
- Der ganze Spaß geht auch andersrum. Wir können aus einem NEA ein Ausdruck kreieren.
- Aber das könnt ihr euch in dem nächsten Video dazu reinziehen. Fassen wir den ultrahocherhitzen Käse nochmal zusammen:
- Aus regulären Ausdrücken lässt sich ein Epsilon NEA bauen. Dazu verwenden wir bestimmte Konstruktionsregeln: Die uns helfen bei den Basisfällen wie die
- leere Menge, das leere Wort oder einem ganz normalen Ausdruck. Verknüpfen wir die Ausdrücke mit Oder, Und oder dem Kleenschen Stern gibt es auch dafür
- bestimmte Regeln zum bauen. Vom Prinzip her zerlegen wir den gesamten Ausdruck in seine Teilausdrücke und konstruieren
- darauf hin den Automaten. Wenn ihr jetzt noch mehr dazu wissen wollt, dann besucht unsre Lernplattform, erzählt
- euren Eltern von uns und haut rein Bis gleich.
Zum Nachlesen
Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den …
Regulärer AusdruckEin regulärer Ausdruck (englisch regular expression, Abkürzung RegExp oder Regex) ist in der theoretischen Informatik eine Zeichenkette, …
Reguläre GrammatikEine reguläre Grammatik ist in der Informatik eine formale Grammatik vom Typ 3 der Chomsky-Hierarchie. Die von solchen Grammatiken erzeugten Sprachen heißen …
Reguläre SpracheIn der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache eine formale Sprache, die einigen Einschränkungen …