Informatik Oberstufe: Endliche Automaten, Teil 1: Einführung
Frank Röhr
https://www.youtube.com/watch?v=5LyruYhfzRc

Transkript (automatisch erstellt)

0:01 [Musik] [Musik] einen wunderschönen guten tag mein name
0:17 ist frank röhr ich wollte ein wenig über endliche automaten reden hallo und herzlich willkommen dazu endlich automaten haben
0:27 verschiedenste wichtige anwendungsmöglichkeiten und geben uns einen kleinen anhaltspunkt darüber was computer können und was computer nicht
0:36 so können ich gehe dann aber jetzt mal direkt so ein bisschen in mitten rein in das thema was ist das also unendliche automat wozu
0:47 dient der die grundsätzliche idee ist wir möchten ein mathematisches modell von einem computer haben ja also und dazu überlegen bei uns dass der computer
0:59 zum bestimmten zeitpunkt für gerade mein computer erhalten bestimmten speicherinhalt den sehen wir als zustand an meinen computer hat gerade den
1:06 zustand dass er eine präsentation zeigt zum thema endlich automaten zb jetzt geben wir etwas in den computer ein zeichen das können wir uns jetzt auch
1:14 als mausklick vorstellen oder ich rede in das mikrofon rein und dadurch ändert sich dieser zustand des computers und wir wollen jetzt herausfinden auf dauer
1:22 ob wir so aussagen treffen können was der computer kann und was er nicht kann er seine mathematischen modelle haben kriegen wir damit raus auf der computer
1:31 grenzen hat und erst mal grundsätzlich was ist überhaupt ein endlicher automatisch sieht das modell aus wir haben erstmal ein alphabet das ist eine
1:44 endliche menge anzeichen wir nehmen gerade buchstaben dafür also abc und so weiter und davon jemanden ein paar in der regel jetzt erstmal für unsere
1:53 automaten ja genau wir nehmen eine endliche menge wieder von zuständen die nennen wir jetzt
2:02 einfach mal cool 0 q1 q2 und so weiter davon gibt es auch nur endlich viele also nicht unendlich sondern definieren vorher für diesen automaten brauchen wir
2:11 ziehen oder so was jetzt definieren wir regeln ich bin den zustand ich kriege es zwar wohl an dich jetzt
2:21 das ist eindeutig für jeden zustand und für jedes zeichen wenngleich sehen wie das aussieht das machen wir grafisch und wir definieren dass einige von diesen
2:31 zuständen die wir haben sind zustände die muss es gar nicht geben ja oder es gibt vielleicht auch nur einen davon ganz oft gibt es nur ein
2:38 es kann aber mehrere davon geben deswegen haben wir eine menge von n zuständen also wollen wir damit mengen klammern und es gibt einen staat zustand
2:47 davon gibt es nur einen ja das ist ein staat zustand davon muss es einen geben davon gibt es auch ein und ich bin jetzt hier erst mal ein
2:52 beispiel wie so ein automat aussehen soll so das sieht jetzt erstmal aus dem komischen wirrwarr aus zum teller spaghetti ne ja ihr seht schon das steht
3:02 irgendwo start und dann steht da cunha kolumnistin zustanden dass steter q1 q2 q3 und so weiter das sind also vier verschiedene zuständig kann aber null an
3:11 und ich habe als und bs das ist das alphabet ja hab es ja immerhin geschrieben wir hab ich habe das jetzt als menge deswegen diese mengen
3:20 klammerte schweiften klammern das sind mengen klammern ich will jetzt gar nicht tief in die mengenlehre eindringen wer von euch
3:28 jetzt nicht weiß was eine menge ist stellt euch einfach vor als mehrere sachen die ich zu einem zusammenfasst und das ist auch ziemlich genau die
3:34 definition ja als alphabet ist hier also a und b mehr buchstaben habe ich hier nicht in diesen automaten ich habe die zustände q1 q2 und q3 00 ist man starrt
3:50 zustand davon gibt es nur einen dass deswegen zeigt der stadtteil drauf und q3 ist ein endzustand in das sehe ich jetzt hier im bild daran das q3 zweifach
3:58 umkreis ist ja daran erkenne ich dass wir würden sich daran und ich hatte eben gesagt es gibt regeln die regeln kann ich dem bild entnehmen zum beispiel 0
4:06 und b es wird wieder zu null also wenn ich im zustand 0 bin und ein b kommt dann lande ich wieder in kundus das sieht er dem
4:13 fall wenn ein anderer fall sieht die 20 und a das wird er nach q1 ja also köhler führt zu q1 wenn ich ihn kommune bin bekomme
4:23 lande ich in 1 was soll das ganze naja ich kann jetzt den automaten ein wort ein wort ist einfach eine folge von buchstaben aus dem alphabet das gebe ich
4:34 in den autos nein der staaten in staad zustand und geht nach den regeln und den eingegebenen buchstaben die zustände
4:42 durch und wenn dann einem endzustand landet akzeptiert das wort und sonst nicht wie muss ich mir das vorstellen es gebe hier wissen automaten abb abb
4:55 bab a good ich fange im staat zustimmt an und das ist cool 0 dann kommt als erstes buchstaben a und das bringt nicht von 0 0 nach q1 das
5:09 heißt der nächste zug stadt ist q1 jetzt folgt ein b in q1 komme ich mit einem b nach q2 das heißt ja nicht so zustand ist jetzt gut
5:19 zwei von co2 aus lande ich mit einem weiteren b wieder in q2 ja das ist unser kreis lande wieder in q2 dann kommt ein a damit lande ich im q3 dann folgt ein b
5:37 damit lande ich wieder in q2 und dann wieder ein a damit komme ich wieder nach q3 das heißt am ende wenn das wort durch ist willig
5:46 in zustand q3 q3 ist ein endzustand der ist doppelt umkreist ist der einzige hier aber es ist vor allen dingen ist es ein ja und wenn ich beim endzustand
5:57 lande dann heißt dass dieser automat akzeptiert das wort also das wort abb ada wird von diesem automaten akzeptiert so jetzt seid ihr dran probiert man
6:11 selber aus ob dieser automat die wörter und so weiter ihr seht sie da unten ob die akzeptiert ich mache meine kurze pause ihr könnt das video dann anhalten
6:20 dass man eben selbst ausprobieren mach das mal so ich gehe jetzt davon aus dass ihr das mal ausprobiert habt ob der automatisch akzeptiert dann kommen wir
6:30 das mal beantworten ada der laut wirklich einmal genau diese zustände durch von cugnaux nach q1 q2 und q3 das heißt er akzeptiert das wort
6:40 abb da lande ich von null aus in q1 und q2 bleibe in q2 hiernach q3 kommen wir wieder zurück
6:50 nach q2 da bin ich am ende das heißt er akzeptiert das wort nicht bab dann wird ebenfalls in q2 und endet im q1 ich komme mir erstmal akku 1 und
7:02 dann bleibe ich dann das heißt diese wörter werden nicht akzeptiert das einzige wort von denen hier was akzeptiert wird ist aber noch ein
7:13 begriff den der wichtig ist am anfang von endlichen automaten die menge der wörter die der automat akzeptiert heißt sprache von ah und nur als kurze
7:22 erklärung dieser automat akzeptiert alle wörter die die folge abi in sich haben und mit einem beenden so ja das war's das war eine ganz kurze einführung in
7:35 die welt der endlichen automaten ich hoffe ihr habt ein bisschen was verstanden wenn nicht schaut es vielleicht nochmal oder schaut es andere
7:42 videos an wie auch immer gut so viel zu den ersten lektionen in etlichen automaten auf wiedersehen