Automatentheorie: Einstieg & DEA
frankjuchim
https://www.youtube.com/watch?v=4d1HcA3Fgc8

Transkript (automatisch erstellt)

0:00 und meinte dann herzlich willkommen zu dieser neuen video reihe es geht um automaten modelle was sind eigentlich automaten modelle und ein erster blick
0:07 auf das erste modell usa das wollen wir diesem video machen los geht's [Musik]
0:18 wir starten direkt mit einem ersten blick in unseren alltag was sind eigentlich automaten wo kennen wir schon automaten
0:26 erst der erste idee ist meistens technische geräte und zwar so was wie ein kaffeeautomat wie ein kaugummi automat wie ein
0:34 süßigkeitenautomat anbahnung oder was weiß ich wo das ist das erste woran denken und wenn man ein bisschen weiter denkt und sich
0:40 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
0:47 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
0:57 und sich schon ein bisschen besser auskennt der weiß auch ein paar seiner sprache kann mit automaten funktionieren mit unser
1:04 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
1:16 funktioniert das auch über das modell von automaten zum beispiel prüfen dann ist die andere der geschlossenen kann man gleich der die
1:23 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
1:32 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
1:42 aufgabe das simulierung da gibt es zwei umsetzung zum einen die technische umsetzung was dann zum beispiel der kaffeeautomat ist den wir schon neben
1:52 als beispiel hatten oder süßigkeitenautomat oder die software umsetzung das wäre dann der parser oder auch überprüfung einer ein gehabt wir
2:00 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
2:08 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
2:15 an und zwar unseren kaffee automaten wieder halt und eine kurze allgemeine satz zum kaffeeautomaten café chaos 40 cent
2:23 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
2:32 verschiedene formate wie man einen automaten darstellen kann und wann hat wer zb ein zustands gab die sehen dann so aus
2:41 oder sind verschiedene kreise und pfeile bevor wir uns ja irgendwie behelfen mit irgendwelchen worten fangen wir an ein bisschen fachsprache zu bilden und
2:49 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
3:00 dass diese kreise beispiel cool sind einige zustände gibt es zwei ganz besondere zustände einmal wie gesagt schon cool und hinten
3:10 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
3:18 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
3:27 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
3:37 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
3:47 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
3:59 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
4:12 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
4:24 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
4:38 zustand und unsere eingabe ist vollständig abgearbeitet das heißt der automat würde diese eingabe 10 20 10 akzeptieren
4:48 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
4:58 unseren kaffee bekommen nichts anderes heißt das wenn wir am ende in einen zustand bestehen ein anderes beispiel werten 10 2020 ein
5:07 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
5:24 fertig 5 ist kein endzustand damit ist das eine nicht akzeptierte eingabe wir würden unser geld in der wieder das geld in dem
5:33 fall zurückgeben als automat das heißt jetzt nochmal zusammengefasst ein automat in diesem fall der deterministische endliche automat
5:41 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
5:51 endzustand befinden auch noch weitere eingaben akzeptieren oder bekommen das ist ganz wichtig ist nicht wir sind einmal im endzustand und verbindendes
5:59 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
6:09 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
6:20 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
6:27 schon über 40 cent sind ja auch wenn ich jetzt die formale definition des deterministischen endlichen auto mal angucken dieses relativ einfach es gibt
6:37 eine menge und zuständen bis 5 haben wir ein eigenes paket waren es 10 und 20
6:46 den 20 cent dann haben wir die zustands übergangs funktionen das wichtigste an einem automaten immer
6:53 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
7:01 weiteren zustand heißt auch jegliche kombination von zustand und eingabe muss einen weiteren zustand ergeben
7:13 das sagte die formale definition hier heißt es in jedem zustand muss ich mit einer mit einer beliebigen eingabe ok weiter
7:20 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
7:29 menge das heißt auch schon ist kaum mehr als einen zustand gehen in unserem fall ist und da gibt es genau einen starts
7:37 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
7:48 stadt sieht wo ist die formale definition eines deterministischen endlich automaten so jetzt habe ich hier noch eine kleine
7:55 aufgabe wird gebracht und zwar entwickelt doch mal selber einen automaten auf dieses kurzes video und entwickler in automaten und dieser
8:04 automat soll eine beliebige zeichenkette annehmen beliebiger länge und sollen nur erkennen steht in dieser zeichenkette mindestens einmal das wort deutsch
8:15 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
8:24 stehen kann egal ob zeichen buchstaben oder zahlen als auch immer er ist klar das gibt
8:32 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
8:40 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
8:49 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
8:59 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
9:08 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
9:17 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
9:26 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
9:36 bleiben wir mal drin wir haben dann ja einmal das wort geil oder die zahlenkombination 0 in unserer zeichenkette oder eingabe gefunden damit
9:44 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
9:52 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
10:01 endliche automaten dann guck dir auf jeden fall noch die weiteren videos an weil da werden bestimmt auch einige seiner fragen beantwortet ansonsten
10:08 stellen sie auch gerne in den kommentaren wenn ich etwas vergessen hat ansonsten sage ich mal und bis zum nächsten video
10:14 [Musik]