Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Informatik Oberstufe: Endliche Automaten, Teil 1: Einführung
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 47 Zeilen
- [Musik] [Musik] einen wunderschönen guten tag mein name
- ist frank röhr ich wollte ein wenig über endliche automaten reden hallo und herzlich willkommen dazu endlich automaten haben
- verschiedenste wichtige anwendungsmöglichkeiten und geben uns einen kleinen anhaltspunkt darüber was computer können und was computer nicht
- 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
- 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
- zum bestimmten zeitpunkt für gerade mein computer erhalten bestimmten speicherinhalt den sehen wir als zustand an meinen computer hat gerade den
- 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
- 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
- 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
- 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
- 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
- automaten ja genau wir nehmen eine endliche menge wieder von zuständen die nennen wir jetzt
- 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
- ziehen oder so was jetzt definieren wir regeln ich bin den zustand ich kriege es zwar wohl an dich jetzt
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- klammerte schweiften klammern das sind mengen klammern ich will jetzt gar nicht tief in die mengenlehre eindringen wer von euch
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- in den autos nein der staaten in staad zustand und geht nach den regeln und den eingegebenen buchstaben die zustände
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- abb da lande ich von null aus in q1 und q2 bleibe in q2 hiernach q3 kommen wir wieder zurück
- 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
- 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
- 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
- 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
- die welt der endlichen automaten ich hoffe ihr habt ein bisschen was verstanden wenn nicht schaut es vielleicht nochmal oder schaut es andere
- videos an wie auch immer gut so viel zu den ersten lektionen in etlichen automaten auf wiedersehen