Von NEA zu regulärem Ausdruck - Automaten und formale Sprachen 8
Informatik - simpleclub
https://www.youtube.com/watch?v=NXK_etZCnQw

Transkript (automatisch erstellt)

0:00 euch gefallen unsere Videos dann kennt ihr nur einen winzigen Teil von the simple Club Übungsaufgaben Lösungswege und spizettel zum Download checkt jetzt
0:07 ab auf the simplekpp.de regulärer Ausdruck zu NEA ist ja easy aber das geht auch andersrum wie man von dem NEA zu einem regulären
0:16 Ausdruck kommt ganz einfach mit einem Gleichungssystem wie das geht der fah der [Musik]
0:24 jetzt okay wir wollen also so einen Freschen NEA in einen regulären Ausdruck umwandeln alles was man dazu braucht ist ein NEA das adensche Lemmer und man muss
0:34 Gleichungssysteme aufstellen und lösen können wie ein NEA funktioniert und was der macht ist ja jedem bekannt was ist jetzt also dieses adensche Lemma das
0:44 Lemma sagt einfach folgendes aus wir haben eine Sprache u und eine Sprache V beide sind Teilmenge eines Alphabets die Sprache u enthält nicht das leere Wort
0:55 als wä es nicht schon genug ist dazu noch l in unserem Alphabet er l jetzt folgende Gleichung l = UL + V können wir daraus gleich l = usternv machen vergess
1:07 all den Käse da oben wichtig ist nur dass aus UL + V = usternv entsteht davon gibt es jetzt noch einen Spezialfall ist v g= die leere Menge dann würde das
1:18 stehen l = UL plus leere Menge wendet man das Lemmer an bekommt man l = u Stern leere Menge also vereinfacht l g leere Menge klar oder was ist jetzt l u
1:30 und v fragt ihr euch was soll das Ganze wieso muss ich so ein Schrott lernen keine Angst wir machen gleich ein Beispiel um so einen Ausdruck aus dem
1:39 NEA aufzustellen geht man folgendermaßen vor Gleichungen aufstellen Gleichung vereinfachen gegebenenfalls mit adenschen lämer weiter vereinfachen bis
1:48 der Lack fertig ist machen wir das mal Schritt für Schritt nehmen wir mal ein stinktnmales Beispiel aus der Uni euer cooler hip Professor klatscht euch
1:56 diesen NEA vor die Nase oder noch besser in Tabellenform wie wir sehen ist der Anfangszustand auch gleich der Endzustand der geile Prof will dass wir
2:06 den Ausdruck finden der die Sprache l von A aus dem Alphabet 01 beschreibt okay dann schritt 1 Gleichungen aufstellen das heißt einfach die Tabelle
2:17 Zeile für Zeile abschreiben in der ersten Zeile haben wir den Zustand P also notieren wir den als LP dann wechselt er mit 0 in Q also
2:26 kommt dahin 0 LQ mit der ein wechselt er in P also fügen wir auch das in unsere Gleichung ein da P der nzustand ist und wir ein NEA haben enthält er das leere
2:36 Wort sumumarum haben wir folgende Gleichung für P LP = 0 LQ + 1 LP + okay nice Sache das ganze machen wir für die restlichen Zustände des Automaten
2:51 auch das heißt wir bekommen für K dann LQ = 0lr + 1 LP für den Zustand R bekommen wir LR R = 1 LP + 1ls für erst bekommen wir dann noch LS = 1lr drückt
3:06 ruhig mal Pause um das nachzuvollziehen am besten ihr merkt euch die Gleichung stellt man auf indem man die Einträge der Zustände mit einem
3:14 Plus verbunden abschreibt ja nice jetzt haben wir also vier Gleichungen für jeden Zustand in der Tabelle als nächstes müssen wir die Gleichung
3:21 einfach ineinander einsetzen bzw vereinfachen dazu benötigen wir erstmal nur die Gleichung LR und LS wir nehmen uns LS und und setzen das in LR ein dann
3:31 bekommen wir LR = 1 LP + 11 1 LR soweit ist das klar oder damit wir weitermachen können brauchen wir jetzt das adensche Lemmer noch mal zur Erinnerung aus UL +
3:44 V wird unv bei unserem Beispiel ist dann 1 LP das V und 11 LR das UL also bekommen wir raus lr= in Klammern 11 Stern 1 LP
3:57 drückt ruhig Pause um das nachzuvollziehen jetzt haben wir also unsere neue LR Gleichung und noch die q und p
4:04 Gleichungen wobei wir LP erstmal wieder nicht brauchen wiedersetzen wir einfach für LR unsere neue Gleichung ein also einfach für LR ersetzen bei der
4:13 Gleichung können wir das adensche Lemmer nicht anwenden und machen gleich weiter jetzt haben wir ja nur noch zwei Gleichungen übrig wieder gleiches Spiel
4:21 wir setzen LQ in die letzte Gleichung LP ein also bekommen wir folgenden kliderer Dutch hol die Waldfee wir haben jetzt ganz schön VI viele LPs lassen wir mal
4:31 die Klammern Weg das heißt wir multiplizieren 0 in die Klammer und dann steht folgendes da LP = 00 in KL 1 1 Stern 1 LP + 01 LP + 1 LP +
4:44 was kann man als Mathematiker damit machen richtig ausklammern also klammern wir LP mal aus jetzt können wir wie gewohnt das Lemmer anwenden und haben es
4:54 auch schon gepackt der erste Teil bildet wieder das UL und das leere Wort ist dann v hieraus kommt dann diese tolle Gleichung das leere Wort können wir dann
5:03 auch einfach weglassen weil ist ja das leere wor weiß du ne das heißt unser Ausdruck beschreibt die gewünschte Sprache wie kann man sich das Verfahren
5:12 jetzt einprägen Schritt ein Gleichung aufstellen Schritt 2 Gleichung vereinfachen dazu das ensche Lemmer oder mathematisches Zeugs
5:20 verwenden Schritt 3 weiter vereinfachen Schritt 4 Aufgabe abgeben und Party machen pS Das Ganze funktioniert auch mit einem dea probiert ruhig mal aus am
5:30 besten wir fassen die wichtigsten Sachen noch mal zusammen wir können mit Hilfe von Gleichungen aus einem NEA einen regulären Ausdruck kreieren dazu
5:37 verwenden wir Gesetze der Mathematik und helfen uns mit dem ischen Lemmer um die Gleichung zu vereinfachen beim Lemmer können wir aus
5:43 l = UL + V einfach l = u Stern vormen noch mal zur Erinnerung die vier Schritte zum Ausdruck Schritt 1 Gleichungen aufstellen Schritt 2
5:53 vereinfachen mit Atems Schum Lemmer oder Gesetzen Schritt 3 weiter vereinfachen Schritt 4 Party machen wenn ihr noch mehr zu zum NEA oder zum dea wissen
6:01 wollt dann kommt einfach auf das simpelclub.de oder ladet euch unsere App runter bis gleich