Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
21. Video Theoretische Informatik WS 2013/14 - Beispiel: endlicher Automat - unistreams
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 28 Zeilen
- wir nehmen jetzt den folgenden automaten die zustands menge q1 q2 als zeichen der eingabe haben wir klein klein b dann haben wir delta wie folgt
- gleich definiert wir haben den start zustand kuh 0 und wir haben die menge der finalen zustände das ist ebenfalls der zustand kuh 0 so und delta ist wie
- folgt definiert ich kann das beispielsweise in einer tabelle hin mal so
- im zustand 0 lese ich ein a und dann komme ich in den zustand q1 eben kuh stand zu stand kuno lese ich ein b dann komme ich in den zustand q2
- im zustand q1 lese ich ein aber dann komme ich wieder nach koh 0 wie komme ich nach q2 so was mache ich jetzt mit so nem
- mit zum automaten mit dem automaten kann ich jetzt rechnen so hatte ich ja gesagt den nutzen war um zu überprüfen ob ein wort eine bestimmte
- eigenschaft hat und ich führe einfach mal so eine rechnung durch und dann kommen wir gleich dazu was noch weiter dahinter steckt
- also eine rechnung in a besteht dann aus der anwendung der übergangs funktion falls wir neben dem wort beispielsweise die eingabe
- sei aber so dann hörten wir jetzt als erstes im wir sind im staat zustand kuno ja das war ja mein start zustand
- dann haben wir unsere eingabe ja so cook in einer tabelle nach da liefert mir das delta ist gerade q1 da ist der automat ließ das a und
- wechselt in den zustand q1 dem zustand q1 lesen wir jetzt noch ein paar das erst zweite
- gucke ich auch wieder minor traveller nach q1 a dann lande ich wieder in kunow wenn ich in como bin und das dritte zeichen lesen das ist das
- b auch wieder mal nachgeguckt kuh 0 b ist co2 das ist jetzt etwas mühselig so hin zu schreiben darum
- vereinbaren war das folgende das war auch so was machen können dass ich nicht nur ein einzelnes zeichen in diese übergangs funktion reinstecken
- kann sondern auch ein ganzes wort und um das eindeutig zu kennzeichnen mache ich meistens und sternchen hier oben dran das heißt ich werde jetzt
- diese übergangs funktion nicht nur einfach an sondern ich werde gleich mehrfach an und das erklären wo eigentlich wie vor einfach wie folgt
- wir gehen einfach schrittweise durch delta von der eigentlich muss ich es formal sauber definieren das mache ich gerade
- und zwar so wie erweitern die jetzt von delta auf delta stern und zwar wie folgt wir erklären delta stern für einen
- beliebigen zustand y das sei gleich das heißt wenn ich nichts lesen bleibt der zwischen einfach erhalten und delta stern von ich bin in einem zustand habe
- ein wort bestehend aus w also irgendwie folge von zeichen und dann ein einzelnes symbol das ist gerade delta von also wir erklären dass auch induktiv
- ich ziehe quasi einmal dieses hier raus und damit bröselig hier sozusagen die ist delta stern auf in zwei anwendungen hier und bin ich ja sozusagen durchmache
- das mache ich jetzt am ein beispiel das wäre also delta von delta stern hu 0,3 das ist sozusagen diese anwendung jetzt hier dieser induktiven definition
- von delta stern auf das akw das ist das gleiche wie delta von delta von
- 0,8 ist jetzt sozusagen auseinander dass ich das zurückführen auf die anwendung von delta auf einzelne zeichen so das ist gleich delta von delta von
- delta kuh 0,3 so und jetzt kann ich das hin aufschreiben
- können uns unsere tabelle wieder nachgucken das q1 q1
- wieder cool und delta von courbet das war gerade co2 also jetzt haben wir sozusagen die übergangs
- funktion ergänzt oder erweitert von einem einzelnen symbol auf ganze wörter
Zum Nachlesen
Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den …
Endlicher AutomatEin endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus …
Akzeptor (Informatik)Ein Akzeptor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Transduktor …
Eindeutiger endlicher AutomatDer eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl.