ENDLICHE AUTOMATEN (mit SUPER MARIO erklärt) | Theoretische Informatik
ฝัง
- เผยแพร่เมื่อ 19 ก.ค. 2024
- Inhalt 📚
Wie der Name bereits vermuten lässt, ist das Fach "Theoretische Informatik" sehr theoretisch. Umso wichtiger ist es, sich die abstrakten Konzepte anhand einfacher Beispiele zu verdeutlichen. Deshalb möchte ich dir in diesem Video anhand von Super Mario World erklären, was man unter einem endlichen Automaten (kurz EA) versteht und aus welchen Komponenten er besteht. Statt Zahlen und Buchstaben verwenden wir praktische Beispiele aus dem Gaming-Alltag.
- Einführung: 0:00
- Was ist ein endlicher Automat? 0:21
- Ein praktisches Beispiel: 0:42
- Komponenten eines endlichen Automaten: 1:26
- Formale Definition eines endlichen Automaten: 2:07
- Wie überprüft man, ob ein Wort Teil einer Sprache ist? 3:28
- Wörter mit einem Automaten erzeugen: 4:36
- Verständnisfragen: 5:15
- NFA vs. DFA: 5:27
- ENDE: 5:54
EQUIPMENT(*)
🎤 Mikrofon amzn.to/3N0CHCL
✂️ Schnittprogramm amzn.to/3CZ217J
💻 Mein Laptop amzn.to/3ikMd5V
🖥️ Bildschirm amzn.to/3ig3yN5
SUPPORT
► Patreon / florian_dalwigk
► PayPal
► Unterstütze mich durch einen Kauf auf Amazon. Für dich entstehen keine Mehrkosten! (*) amzn.to/3LgyglY
SOCIAL MEDIA
💬 Discord: / discord
💡 Website: www.florian-dalwigk.de
📱 TikTok: / florian.dalwigk
🤳 Instagram: / florian.dalwigk
🐦 Twitter: / florian_dalwigk
📧 E-Mail: mailto:info@florian-dalwigk.de
Das Spiel "Super Mario World" wurde von Nintendo entwickelt. Von dort stammen auch die hier im Video verwendeten Bilder der Spielfiguren und Items.
Video zur Chomsky-Hierarchie 📼 [Folgt]
NFA in DFA umwandeln 📼 • NFA in DFA umwandeln |...
NFA in DFA umwandeln (Beispiel) 📼 • NFA in DFA umwandeln (...
(*) Bei den Amazon-Links (https.//amzn.to/???????) handelt es sich um Affiliate-Links. Wenn du etwas über diesen Link kaufst, bekomme ich eine kleine Provision. Der Preis ändert sich nicht, wenn du über diesen Link einkaufst. Vielen Dank für deine Unterstützung.
3. Ist ein mögliches Wort
Kürzestes: 🐢
Ich habe eigentlich keine Ahnung davon, aber ich finde du erklärst sehr gut
Richtig :) Und vielen Dank für dein Lob!
Echt Klasse! Für einen Spätzünder in der Informatik (Ü30), wie ich einer bin, sind das echt tolle Beispiele! 😁
Toll, das freut mich 🙂
Es ist nie zu spät ;)
Coole Idee die "Super-Mario" Symbolik zu benutzen ;)
Danke ;) Fand ich an dieser Stelle passend!
Super Video, lustiger weise haben wir das gerade im Unterricht (10. Klasse). Sehr gut verständlich !
Danke :)
Mega starkes Video!
Eine spannende Aufgabe zum Überprüfen des Erlernten in einem zukünftigen Video/zukünftigen Challenge wäre die Interpretation eines "echten" endlichen Automaten.
Das hätte ich noch spannend gefunden und hätte mir als nicht-Informatiker beim Abspeichern des Erlernten geholfen, aber das hätte nicht auch noch alles ins Video gepasst.
Danke für die Anregungen!
Deine Erklärungen sind einfach immer klasse 👌🙏😀
Das freut mich, danke!
Vielen Dank für das Video. Schreibe in einem Monat die Klausur darüber, wäre cool wenn bis dahin weitere solcher Video kommen :D
Gerne! Dazu werden noch weitere Videos kommen. Ich wünsche dir viel Erfolg beim Lernen!
Ich bin dir sooo dankbar, dass du das ganze so gut verpackt hast! Danke!
Sehr gerne :)
Wow ich hab noch nie was davon gehört und du hast es mir in 5 min beigebracht! Super gut! 🐢
Gerne :)
Sympathisch und interessant, vielen Dank für die Freude und Hilfe! :)
Gerne doch :)
Hatten das gerade heute in der Vorlesung, war zwar schon klar doch dein Video hat das ganze nochmal verstärkt.
Wirklich? Was für ein Zufall ;)
Mega geiles Beispiel im Titelbild xD ... eig. sehr verständlich für alle und schon extrem selbsterklärend. Daumen hoch.
Danke dir :)
Super gut. Gefällt mir sehr :D
Das freut mich :)
Super erklärt, sehr hilfreich.
Top! Großartig erklärt! Vielen Dank! :)
Gerne 🙃
Richtig gut erklärt! Eben noch Fragezeichen vor den Augen durch die ganzen Symbole, jetzt Super Mario ;)
Hervorragend 😃
Du hast gerade meine info klausur morgen gerettet, danke!
Super :) Ich wünsche dir viel Erfolg!
einfach klasse,,,sehr gut erkl'rt,, vielen vielen vielen dank Super Mario :)))))
😅
Danke hat gut in der Klausur geholfen 👍
Hervorragend, so soll es sein 😊
Sehr schönes Beispiel !. Endlich ein endlichen Automat Verstanden xD
Nice, das freut mich :)
Wie gut, dass ich darüber heute teilweise meine Vorabi Klausur geschrieben hab :D
Wie lief's?
@@Florian.Dalwigk Bestens, Info ist jetzt nie so ein großes Problem - bei dem Niveau aber auch kein Wunder :D
Super!
Danke für dieses Video
Gerne, freut mich, dass ich dir weiterhelfen konnte :)
Meine Schüler schreiben gerade eine Kursarbeit mit diesem Beispiel ;) Danke für die Inspiration. Wobei ich näher an Super Mario World vorgegeben habe, dass Feuer-Mario durch Koopa direkt klein werden soll :D
Ah, wie cool 😎
Weiß zwar schon wie Automaten funktionieren, jedoch fand ich die Mario Analogie einfach zu gut um es mir nicht anzuschauen.
Super :)
Dass hast du sehr gut erklärt!
Danke dir!
Ich glaube nur das 3. ist in der Supermariosprache, da 1. bei großem Mario endet und 2. bei kleiner Marioendet und damit beides nicht in einem endzustand endet. Das kürzeste Wort müsste Kooper sein.
Dem stimme ich voll und ganz zu
Stimmt!
@@marvjojo989 Ist korrekt :)
Lange gehadert, endlich verstanden! Danke👍
Hervorragend, so soll es sein 😎
Faszinierend
:)
So gut!
😊
Ehrenmann. Legenär erklärt
😊
Einfach gut, so verstehe auch ich das :-)
Perfekt
sehr informativ
Danke
danke gut erklärt
Sehr gerne!
Danke für das Video! Nur eine Frage hätte ich noch: ,, Sind Automaten Graphen und die Mariozustandsmöglichkeiten sind damit Nodes?"
Ja, so kann man das auffassen.
Sehr geil!
:)
@@Florian.Dalwigk Kurze Frage: Darf dieser endliche Automat auch 2 Endzustände haben? Also beispielsweise mit dem Symbol "Flagge", wodurch das Level als bestanden gilt?
Kleiner, erwachsener und heißer Mario müssten dann diesen Pfeil zur Zustandsänderung mit der Flagge haben, aber sind 2 Endzustände grundsätzlich erlaubt?
Toll, das war hilfreich ! Viele Grüße von der LMU München.
Vielen Dank :) Viele Grüße zurück!
@@Florian.Dalwigk Hast du auch Videos über HMM & Viterbi? Konnte da noch kein deutsches finden. Danke
Gutes Video!
Dankeschön!
Danke dir für das video
Gerne!
Du rettest mein Studium 🙌🏽❤️❤️
:)
Gutes Video und schöner Vergleich.
Hilft wahrscheinlich Vielen, die das in der Schule haben.
Danke! Ja, das ist mein Ziel ;)
👍
Genial! Kürzestes: Cooper! Ich nehme mal an, dass der Automat auch mehrere Enden haben kann, die ein Teil der Wortliste sein müssen. Dieses Denkkonzept gefällt mir sehr! Auch das, wie man das alles mithilfe von Super Mario verdeutlichen kann. Wie passen da invisibility Frames rein? Wäre das dann so, als gäbe es den Cooper nicht? (Wort Ignore certain Words of in-case-Wortliste?)
Danke dir. Könnte man so sehen. Invisible Frames wären in meinen Augen eher so etwas wie das leere Wort ;)
@@Florian.Dalwigk , das leere Wort? Moment: das kann es nicht sein. Es gibt noch das Wort Pit, das trotz der Invisibility-Frames zum letzten Wort führt… Nur Spaß, danke für die Denkanstöße! Ich sehe schon. Da kommt man vom hundertsten ins tausendste. Herrlich!
Ich will im WS ein Informatikstudium anfangen. Der Prof meinte heute beim Tag der offenen Tür, dass endliche Automaten ein knackiges Thema seien, auf das man sich ggf vorbereiten sollte. Jetzt habe ich dein Video gesehen und sehe nicht viel mehr Lernaufwand als die "Grammatik" zu lernen. Ich hoffe ich werde nicht leichtsinnig xd
Und wie läuft es?
@@tungilgynch6044 ich skippe Mathe bisher komplett xD Der Rest läuft super
@@tungilgynch6044 danke der Nachfrage ig
Das kuerzte Wort ist: Cooper. Nochmal danke fuer das Video, ich habe es zum lernen fuer eine Klassenarbeit benutzt. Weiter so.
Viel Erfolg für die Klassenarbeit
Cooles Video und verständlich erklärt. Aber wozu benötigt man sowas in der Praxis?
Meine Lösungen:
_Bedeutung der Buchstaben ganz unten_
a) Verständnisfragen
1. F, K, P, F, K = Falsch
2. P, K = Falsch
3. F, K, F, K, K, K = Richtig
b) Kürzestes Wort
K
*Bedeutung der Buchstaben*
P = Pilz
F = Feuerblume
K = Koopa
das ist ein gutes video kamerade!
Vielen Dank :)
@@Florian.Dalwigk 2 auf Test nur mit Mario!
Richtig cool 😎 Herzlichen Glückwunsch!
stark
😁👍
Eis gutes Video! Passend für meine 6.-Klässler :)
6. Klasse?!
@@Florian.Dalwigk Automatentheorie kommt tatsächlich als Thema im Lehrbuch für die 5./6. Klasse vor (C.C.Buchner Verlag). Natürlich völlig "unmathematisch" und deswegen ist mir das Mario-Beispiel viel lieber, als Einstiegsbeispiel als "die Zustandstabelle eines Getränkeautomaten" o.Ä.
Ah, gut zu wissen, danke!
Super erklärt! Ich check nur überhaupt nicht, wie einen das beim Programmieren weiterbringen soll.
Das wird z. B. benötigt, um herauszufinden, ob ein Programm frei von Syntaxfehlern ist.
Top, Video! Im Unterricht leider viel zu theoretisch erklärt wurden.
3. ist in der Super Mario Sprache + Ein einzelner Koopa ist das kürzeste Wort
Das freut mich :) Gern geschehen!
Kann man einen Webbrowser als Automaten bezeichnen und wenn ja, welcher Art?
Ist bei dem dargestellten Automaten erlaubt, dass der große Mario einen weiteren Pilz ist (und einfach groß bleibt)? Also Zustand ändert sich nicht, wenn das nächste Event (hier "Pilz essen") eintritt oder muss hierfür explizit ein Pfeil auf den gleichen Zustand zeigen. Hier also Pfeil von großer Mario auf großer Mario und daneben ein Pilz.
Gehe ich mal von aus, meistens zeichnet man die auf sich selbst zeigenden Pfeile nicht auf.
Nunja, es steht nicht dort, also wäre es nicht erlaubt. Man könnte das aber ergänzen.
Coolll
:)
Wann kommen die Linux Videos? Freu mich schon drauf.
Schon sehr bald. Ich arbeite aktuell an den ersten dreien.
5:20 Cooper
Yes
Schön veranschaulicht!
Aber müsste nicht eigentlich noch beim Großen Mario eine Schleife mit einem Pilz sein? Wenn man einen zweiten Pilz aufsammelt bleibt man ja in dem Zustand
Könnte man hinzufügen, ja
Hallo, bin ich im Fach "Theoretische Informatik" stecken geblieben. Ich bräuchte Hilfe bei DEAs/NEAs/Kellerautomaten und Turingmaschinen d.h. jemand, der Coach ist oder Nachhilfe im Bereich gibt? (Die Theorie habe ich viele Male durchgearbeitet, brauche aber Übungen und jemanden zur Seite, um zu sehen was ich falsche mache). An wen könnte ich mich da am besten wenden?
Pünktlich zur Prüfung
Perfekt :)
Jetzt noch Kellerautomaten mit Mario bitte 😂
Kellerautomaten kommen demnächst ;)
Ach ich schrieb gestern darüber eine Klausur geschrieben ;(
Schlechtes Timing - hab aber trotzdem alles eigentlich gewusst :d
Sorry :( Aber gut, dass du trotzdem wusstest, was zu tun ist ;)
@@Florian.Dalwigk es war sogar so ausführlich, dass ich vergaß wie man einen einfachen Satz baut! :D
Ist das Prinzip auch auf Fpga s anwendbar?
Inwiefern?
Ich bin so froh das ich zur Wirtschaftsinformatik gewechselt bin und keine theoretische Informatik mehr brauch :-)
Bei welchem Info Studiengang braucht man denn theoretische Informatik? Wir machen den EA nämlich gerade in der Schule (:
Passt jetzt nicht zum Thema des Videos, aber einen Vorteil bringen Klausuren von Zuhause aus schon:
Ich darf Entwicklungsumgebungen nutzen :D
Das kann ein Vor-, aber auch ein Nachteil sein!
Das kürzeste Wort wäre dann der Koopa ^^
Richtig!
gibt es eine Möglichkeit, meinen Code (zb Java) in so einen Automaten unzuwandeln?
Ja
wie denn? und geht das auch automatisiert?
@@Florian.Dalwigk
Wie werden nicht definierte Überführungsfunktionen gehandhahabt? Is das ein Syntax Error?
Was ist eine nicht definieren Übergangsfunktion?
@@Florian.Dalwigk in deinem Beispiel, wenn man als großer Mario einen Pilz sammelt
Achso. Ja, das ist dann ein Syntaxfehler.
das kürzeste Wort ist die Nummer 2,richtig?
30 Folien skip... Ich dank dir xD
Gerne :)
Lieber Florian, wo ist das Chomsky Video . ;)
Kommt noch
Und was sind akzeptor und Transduktor? Was sind die unterschiede?
Detektor sagt mir nichts
@@Florian.Dalwigk ich meine natürlich Transduktor
Ah, das sagt mir etwas :)
@@Florian.Dalwigk könntest du mir erklären wie ein Transduktor funktioniert?
Das kürzeste Wort ist ein Cooper: kleiner Mario -> tot
:)
(:
3 ist richtig dass kürzeste Wort ist kooper
Kürzeste Wort ist Cooper, glaube ich
Korrekt!
Übermorgen mündl. Abi 🥶
Ich drücke dir die Daumen 🤞
Wir benutzen dabei die NTPS Gramatik
ok
Dieser Super Mario wird nie ein Level schaffen, weil er immer von einem Koopa getötet werden muss
Das stimmt :( Hier muss noch etwas nachgebessert werden ;)
Ich nehme Nummer vier nur ein koppa 😁
Na ja, in Super Mario World wird man nach einem Hit eigentlich sofort wieder klein, selbst mit Feuer Mario, aber die Erklärung hat auch gepasst, thx!
Gerne
Wieso können Dozenten ihre Skripte nicht so schreiben oder zumindest ein praktisches Beispiel wie dieses geben anstatt 10 Seiten lang wissenschaftliches Zeug zu labern, was niemand außer sie selbst versteht? Vielen Dank!
Sehr gerne 😊
Ich finde es sehr traurig dass es Nur den Endzustand ‚tod‘ gibt
:(
3
👍
Das kürzeste Wort: 🐢
Richtig!
Das kürzeste word ist ist : *Koopa*
Genau!
3 endet
?
Kommentar für den Algorithmus
Antwort auf den Kommentar für den Algorithmus.
Kuhper
🐢
1:16 Das stimmt aber für die originale SNES Version gar nicht; man wird direkt klein. Deabonniert!
Da kann ich mich nur anschließen. Algorithmen verstehen lässt langsam nach, kaum aushaltbar.
@@tomchenkov4910 :(
Du bist Gott
😇
Und was bringt mir das jetzt? Also nur mal so gefragt
Endliche Automaten sind ein Modellierungswerkzeug in der Informatik. Wenn man eine solche Modellierung versteht, kann man bestimmte Probleme einfacher lösen.
Eine theoretische Anwendung ist die Erkennung, ob ein bestimmtes Wort Teil einer (regulären) Sprache ist.
Spannender finde ich die Anwendung, eigene Automaten zu bauen. Z.B. könnte man damit einen Roboter programmieren, der einen Weg durch ein Labyrinth findet (oder die Wohnung reinigt).
Du bist Gott
Warum wusste ich das bisher noch nicht?