Regulären Ausdruck in NEA umwandeln - Automaten und Formale Sprachen 7
Informatik - simpleclub
https://www.youtube.com/watch?v=uLpxchiMJL0

Transkript (automatisch erstellt)

0:10 Moin Leute, Ihr wisst bescheid über die Automaten, ihr wisst bescheid über reguläre Ausdrücke… Dann können wir das jetzt connecten.
0:17 Heute ziehen wir uns mal rein, wie man aus nem Regulären Ausdruck ein NEA basteln kann. uuuund bitte!
0:23 Also jut! Wir wir ja schon gelernt haben existiert zu jedem regulären Ausdruck ein endlicher Automat.
0:33 Wir konstruieren dazu den nichtdeterministischen endlichen Automaten. Abgekürzt den NEA.
0:39 Aber nicht irgendein NEA sondern den mit Epsilon Übergängen, also den Epsilon NEA. Was war an dem nochmal so besonders?
0:47 Ah jo mit dem dürfen wir einfach so yolonese mäßig in ein anderen Zustand jumpen ohne ein Zeichen zu lesen.
0:54 Nice! Zurück zum Thema: Vom Prinzip funktioniert dat ganze so: Wir
0:58 bekommen einen Ausdruck , diesen zerlegen wir dann in Teilausdrücke und daraus konstruiere ma dann den Automate.
1:04 Isch easy! Damit ma das mache könne, gibt’s bestimmte Konstruktionsregeln.
1:09 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
1:16 leere Menge enthält, würde das ganze so aussehen: Wir haben ein Anfangszustand und einen Endzustand.
1:22 Allerdings passiert eigentlich rein gar nix. Naja macht ja auch Sinn, in der leeren Menge steht ja auch nischt drin.
1:28 Der nächste Basisfall betrifft das leere Wort: Hier erzeugen wir ein Anfangszustand, einen Endzustand und verbinden das mit der Epsilon
1:36 Kante. Also dem Pfeil und so, weißte?
1:39 Der dritte Basisfall ist ähnlich wie das leere Wort. Hier haben wir aber ein Symbol oder Wert aus dem Alphabet, zum Beispiel a.
1:46 Wieder erzeugen wir ein Anfangszustand und einen Endzustand und verbinden den ganz normal mit dem Wert den wir bekommen.
1:52 Verbindungen von Ausdrücken Okay soweit so gut! Was passiert, wenn wir Ausdrücke haben wie diese hier:
1:58 Logisch dafür gibt es auch Regeln. Wie überall.
2:02 RS oder auch R mal S ist die Verkettung. Damit hier das Wort akzeptiert werden kann, wird erst der Ausdruck R vom Anfangszustand
2:10 bis zu seinem Endzustand durchlaufen. Danach gehen wir mit Epsilon in den Anfangszustand vom zweiten Ausdruck S und durchlaufen den
2:17 bis zum Ende. Einfach gesagt wir verbinden beide Ausdrücke mit dem Epsilon Übergang.
2:22 Klar oder? Jut dann gehen wir mal die anderen Fälle durch.
2:26 Was ist wenn wir eine Alternative haben. Sprich R+S.
2:29 Da es ja Alternative heißt müssen wir die Ausdrücke auch aufteilen. Das heißt wir beginnen mit einem Anfangszustand.
2:36 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
2:45 Epsilon zum Endzustand. Keine Angst wir schauen uns dazu noch ein Beispiel an.
2:50 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:
2:57 Wir starten ganz normal in einem Anfangszustand. Gehen dann mit Epsilon in den Ausdruck.
3:02 Und durchlaufen diesen. Anschließend gelangen wir wieder mit Epsilon in den Endzustand.
3:08 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
3:17 leere Wort akzeptieren können. Holla die Waldfee!
3:20 Was könnt ihr euch merken: Um aus einem regulären Ausdruck eine Epsilon NEA zu bauen, muss man gewisse Regeln anwenden.
3:27 Beispiel Von Ausdruck zu NEA Machen wir gleich mal ein Beispiel, damit es klarer wird.
3:30 Sagen wir mal so nen frehser Dude will aus diesem Ausdruck nen Automaten konstruieren: (a+b)*ab Wir
3:43 haben einmal a+b, das ganze dann in der Kleenschen Hülle und das verkettet mit ab.
3:48 Fangen wir mal mit a+b an. Den Ausdruck a können wir ja ganz einfach mit dem Basisfall hinschreiben
3:55 Sprich Zustand verknüpft mit a zum Endzustand. Jetzt fügen wir das + bzw. oder ein: Wir starten im Anfangszustand und können
4:03 mit Epsilon in a wechseln oder in den zweiten Ausdruck. Der zweite Ausdruck wäre dann einfach b.
4:09 Joa geil. Als nächstes fügen wir den Kleenschen Stern hinzu.
4:13 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.
4:23 Die verbinden wir jetzt mit dem Epsilon Übergang. Jetzt müssen wir nur die Wiederholung einfügen.
4:28 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.
4:37 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
4:46 a und b mit den entsprechenden Bopeln an den alten Endzustand dranhängen. Damit sind wir durch und haben unsern Automaten konstruiert.
4:53 Was kann man sich merken: Um aus einem regulären Ausdruck einen Automaten zu konstruieren.
4:59 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
5:07 auf unsere Lernplattform da ist auch alles zu finden. Probiert selbst mal aus einem Ausdruck ein NEA mit den gegebenen Regeln zu konstruieren.
5:15 Der ganze Spaß geht auch andersrum. Wir können aus einem NEA ein Ausdruck kreieren.
5:20 Aber das könnt ihr euch in dem nächsten Video dazu reinziehen. Fassen wir den ultrahocherhitzen Käse nochmal zusammen:
5:25 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
5:33 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
5:42 bestimmte Regeln zum bauen. Vom Prinzip her zerlegen wir den gesamten Ausdruck in seine Teilausdrücke und konstruieren
5:48 darauf hin den Automaten. Wenn ihr jetzt noch mehr dazu wissen wollt, dann besucht unsre Lernplattform, erzählt
5:53 euren Eltern von uns und haut rein Bis gleich.