Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Automatentheorie: Einstieg & DEA
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 68 Zeilen
- und meinte dann herzlich willkommen zu dieser neuen video reihe es geht um automaten modelle was sind eigentlich automaten modelle und ein erster blick
- auf das erste modell usa das wollen wir diesem video machen los geht's [Musik]
- wir starten direkt mit einem ersten blick in unseren alltag was sind eigentlich automaten wo kennen wir schon automaten
- erst der erste idee ist meistens technische geräte und zwar so was wie ein kaffeeautomat wie ein kaugummi automat wie ein
- süßigkeitenautomat anbahnung oder was weiß ich wo das ist das erste woran denken und wenn man ein bisschen weiter denkt und sich
- ein bisschen auskennt dann weiß man schon so überprüfungen von eingaben das können automatisch auch übernehmen ja zum beispiel wie kriegen wir eine e-mail
- adresse ist dass eine korrekte eingabe oder das ist keine brücke der eingabe die kann man alle mit automaten backen wer dann noch ein bisschen weiter denkt
- und sich schon ein bisschen besser auskennt der weiß auch ein paar seiner sprache kann mit automaten funktionieren mit unser
- japaner sagen wir mal unser java editor oder unser visual studio code oder oder oder sagte da sind noch klammern auf zu wenige oder kanada zu zu wenig wenn es
- funktioniert das auch über das modell von automaten zum beispiel prüfen dann ist die andere der geschlossenen kann man gleich der die
- anzahl eröffnet also was funktioniert der automaten und wir wollen uns jetzt nach einem kurzen blick von auf die theorie die automaten noch mal einen
- bitten also zuerst die theorie was sind automaten es gibt einmal die automat er ist ein abstraktes gebilde modell zur lösung von einem problem oder eine
- aufgabe das simulierung da gibt es zwei umsetzung zum einen die technische umsetzung was dann zum beispiel der kaffeeautomat ist den wir schon neben
- als beispiel hatten oder süßigkeitenautomat oder die software umsetzung das wäre dann der parser oder auch überprüfung einer ein gehabt wir
- werden uns hauptsächlich in dieser videoreihe mit dieser seite beschäftigen der modellierung des ganz die umsetzung haben wir schon mal zum teil gemacht ist
- dann aber auch gar nicht mehr so schwer wenn man die modellierung einmal richtig hat das zu kurzen einführung jetzt gucken wir mal eben ein erstes beispiel
- an und zwar unseren kaffee automaten wieder halt und eine kurze allgemeine satz zum kaffeeautomaten café chaos 40 cent
- betragen muss passend eingebauten werden sonst gibt es das geld zurück doch was auch immer und wir akzeptieren nur zehn und 20 cent müssen nun gibt es
- verschiedene formate wie man einen automaten darstellen kann und wann hat wer zb ein zustands gab die sehen dann so aus
- oder sind verschiedene kreise und pfeile bevor wir uns ja irgendwie behelfen mit irgendwelchen worten fangen wir an ein bisschen fachsprache zu bilden und
- gucken uns mal an was sind denn dieser kreise mit zahlen und buchstaben drinnen das sind nämlich zustände ja das ist ein zustand graf und
- dass diese kreise beispiel cool sind einige zustände gibt es zwei ganz besondere zustände einmal wie gesagt schon cool und hinten
- q4 die neat man auch schon dass sie ein bisschen besonders sind polen hat ein pfeil der aus dem nichts kommt da steht start drauf das ist der staat zustand
- und wenn es dem staat zustand gibt soll jetzt auch im endzustand geben und das ist in unserem fall profil da drüben und zwar q4 doppelt gekreist heißt nichts
- anderes als endzustand das ist ja schon mal es kann mehrere and zustände geben aber nur einen dazu statt dann können wir ganz weile noch welche
- haben das sind über genk wer sich alleine an gemeckert aber zum beispiel überall wo er zehn und zwanzig dann steht und zum teil ist von einem zustand
- zum nächsten was sind übergänge die beschreiben nun wie ich von einem zustand in den nächsten kommen manchmal bekomme ich in von q1 in elf mann zu in
- q1 mit dem ich zehn cent in den automaten werden & co 0 in q2 um mich in dem ich 20 cent in die automaten ein werfe so und wie
- funktionieren nun die eingaben wenn ich jetzt zb einem jahre 10 20 10h am ende 40 cent eingebrochen das müsste der automat akzeptieren als eingabe ich
- jetzt einwerfen lade ich von cominco 1 dann 20 ländern von q1 in q3 wir haben wieder zehn dann lass dich in q4 hier ist doppelt gekreist ist einem
- zustand und unsere eingabe ist vollständig abgearbeitet das heißt der automat würde diese eingabe 10 20 10 akzeptieren
- zum beispiel wir in 2010 denn genau 40 cent das heißt er hätte das passend eingeworfen das geld und wir hätten das geld passt eingebrochen und würden damit
- unseren kaffee bekommen nichts anderes heißt das wenn wir am ende in einen zustand bestehen ein anderes beispiel werten 10 2020 ein
- gehen wir erstmal mit 10,0 in q1 mit 20 von gut 21 in q3 und dann gehen wir von gut 23 cent dann hätten wir ja 50 cent bezahlen
- fertig 5 ist kein endzustand damit ist das eine nicht akzeptierte eingabe wir würden unser geld in der wieder das geld in dem
- fall zurückgeben als automat das heißt jetzt nochmal zusammengefasst ein automat in diesem fall der deterministische endliche automat
- akzeptiert eine eingabe genau dann wenn die eingabe vollständig abgearbeitet ist und wir uns im endzustand befinden wir können natürlich wenn wir uns einmal im
- endzustand befinden auch noch weitere eingaben akzeptieren oder bekommen das ist ganz wichtig ist nicht wir sind einmal im endzustand und verbindendes
- ende sondern erst wenn die eingabe vollständig abgearbeitet ist 5 ist noch eine kleine besonderheit wir sehen in q5 den pfeiler übergänge rheinweiler rein
- aber nicht wirklich raus weil diese zehn und zwanzig die denn da kommen die sind nur wieder in von q5 in kusel wenn uns das dem beispiel denken 5 heißt wir
- haben zu viel gezahlt schon bereits dann wird noch weiter geld eingeworfen das funktioniert ja nicht so kommen wir niemals um mehr geld ein werken und
- schon über 40 cent sind ja auch wenn ich jetzt die formale definition des deterministischen endlichen auto mal angucken dieses relativ einfach es gibt
- eine menge und zuständen bis 5 haben wir ein eigenes paket waren es 10 und 20
- den 20 cent dann haben wir die zustands übergangs funktionen das wichtigste an einem automaten immer
- und 2 die züchter die übergangs funktion sagt uns wenn wir uns in einem züchter befinden und eine eingabe kommt gehen wir in allen ganz bestimmten
- weiteren zustand heißt auch jegliche kombination von zustand und eingabe muss einen weiteren zustand ergeben
- das sagte die formale definition hier heißt es in jedem zustand muss ich mit einer mit einer beliebigen eingabe ok weiter
- damit jeder eingabe muss nicht von einem zustand aus wald da gibt es eine menge an end zuständen dass in den gehwegen f das ist eine
- menge das heißt auch schon ist kaum mehr als einen zustand gehen in unserem fall ist und da gibt es genau einen starts
- gestand hier couleur übrigens meistens kino der stadt zustand klein es ist aber auch genau ein bestand nicht zwei oder auch nicht gar keiner es gibt genau eine
- stadt sieht wo ist die formale definition eines deterministischen endlich automaten so jetzt habe ich hier noch eine kleine
- aufgabe wird gebracht und zwar entwickelt doch mal selber einen automaten auf dieses kurzes video und entwickler in automaten und dieser
- automat soll eine beliebige zeichenkette annehmen beliebiger länge und sollen nur erkennen steht in dieser zeichenkette mindestens einmal das wort deutsch
- es ist ein bisschen ein klargemacht dass eingabe alphabet ist vorgegeben das ist natürlich und fragezeichen wobei das fragezeichen für jedes andere zeichen
- stehen kann egal ob zeichen buchstaben oder zahlen als auch immer er ist klar das gibt
- wir sind gelaufen ich hoffe das hinbekommen wir gucken uns einmal lösen gemeinsam an das wäre der zustands grad wir sehen schon wir haben hier
- 02 12 und q3 vielleicht hast du noch mehr zustände weniger wird glaube ich schwer ansonsten schreibt gerne in die kommentare vielleicht habe ich eine
- lösung gesehen ja in kunow kommen wir bleiben wir erst mal so lange bis ihr ein elbe kommen wenn wir kein elbe kommen bleiben wir in 40 weil dann
- haben wir noch nicht der anfang ist wort wenn wir jetzt in q1 sind dann haben wir sozusagen ein l schon bekommen für jedes weitere ll bleiben wir natürlich in q1
- weil wir waren ja wohl wieder mit einem o gehen denn co2 und mit jedem anderen zeiten gehen wieder zurück da haben wir nun ergab
- die zwei haben wir schon entstehen das heißt jetzt warten muss der nächste buchstabe auf jeden fall nl sein ansonsten hoffen wir wieder ganz zurück
- in kohle bekommen wir ein links ein lkw in q3 dass in unseren zustand und ihr seht auch wenn man genau hinguckt ich komme aus gut 33 mehr raus weil da
- bleiben wir mal drin wir haben dann ja einmal das wort geil oder die zahlenkombination 0 in unserer zeichenkette oder eingabe gefunden damit
- ist das wort die eingabe auf jeden fall akzeptiert dass der graf wenn man das als formale definition machen sie den die da drüben einmal das gehe ich jetzt
- nicht mehr einzeln durch das kannst du dir sicherlich auch immer so angucken hast du ja auch eine fragen zum thema automaten sowie die feministische
- endliche automaten dann guck dir auf jeden fall noch die weiteren videos an weil da werden bestimmt auch einige seiner fragen beantwortet ansonsten
- stellen sie auch gerne in den kommentaren wenn ich etwas vergessen hat ansonsten sage ich mal und bis zum nächsten video
- [Musik]
Zum Nachlesen
Endlicher AutomatEin endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus …
Eindeutiger endlicher AutomatDer eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl.
Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den …
Automat (Informatik)Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.