Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Von NEA zu regulärem Ausdruck - Automaten und formale Sprachen 8
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 38 Zeilen
- euch gefallen unsere Videos dann kennt ihr nur einen winzigen Teil von the simple Club Übungsaufgaben Lösungswege und spizettel zum Download checkt jetzt
- 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
- Ausdruck kommt ganz einfach mit einem Gleichungssystem wie das geht der fah der [Musik]
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- NEA aufzustellen geht man folgendermaßen vor Gleichungen aufstellen Gleichung vereinfachen gegebenenfalls mit adenschen lämer weiter vereinfachen bis
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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 +
- 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
- drückt ruhig Pause um das nachzuvollziehen jetzt haben wir also unsere neue LR Gleichung und noch die q und p
- 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
- 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
- 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
- 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 +
- 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
- 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
- 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
- jetzt einprägen Schritt ein Gleichung aufstellen Schritt 2 Gleichung vereinfachen dazu das ensche Lemmer oder mathematisches Zeugs
- 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
- 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
- verwenden wir Gesetze der Mathematik und helfen uns mit dem ischen Lemmer um die Gleichung zu vereinfachen beim Lemmer können wir aus
- l = UL + V einfach l = u Stern vormen noch mal zur Erinnerung die vier Schritte zum Ausdruck Schritt 1 Gleichungen aufstellen Schritt 2
- 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
- wollt dann kommt einfach auf das simpelclub.de oder ladet euch unsere App runter 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äre SpracheIn der theoretischen Informatik ist eine reguläre Sprache oder reguläre Menge oder erkennbare Sprache eine formale Sprache, die einigen Einschränkungen …
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 …
Pumping-LemmaPumplemma (auch Schleifensatz genannt) beschreibt in der theoretischen Informatik eine Eigenschaft bestimmter Klassen formaler Sprachen. ... sei eine reguläre …