Zum Inhalt springen
L

Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).

DEA - Automaten und Formale Sprachen 2

Informatik - simpleclub8:28 228.841 Aufrufe veröffentlicht Auf YouTube

Das Wichtigste aus dem Video

Tipp auf eine Zeit – das Video springt genau dorthin.

Transkriptautomatisch erstellt · 75 Zeilen
Herunterladen
  1. Guuden Tach ihr Rabauken! Heute beschäftigen wir uns mit dem D E A….
  2. D….E….A hmm das steht doch für Drug Enforcement Administration oder? Ja auch aber darum gehts heute nicht!
  3. Bei uns steht DEA für Deterministische Endliche Automaten Oh man und ich dachte es kommt was cooles :D
  4. Keine Sorge so uncool ist das gar nicht, warum das seht ihr nach dem Intro. So gucken wir mal rein: Was ist so ein DEA?
  5. DEA steht wie gesagt für Deterministischer Endlicher Automat. Automat?
  6. Etwa wie diese geilen Kaugummi Automaten vor der Schule? Jap so änhlich, allerdings kommen haben die hier nix mit Kaugummis zu tun.
  7. Der DEA ist ein Berechnungsmodell für Sprachen. Das heißt damit kann entschieden werden ob bestimmte Wörter in einer Sprache sind oder
  8. eben nicht. Nochmal zur Erinnerung:
  9. Was war eine Sprache noch mal? Eine Sprache ist eine beliebige Menge von Wörtern aus einem Alphabet.
  10. Ein Alphabet ist ne endliche Menge von Symbolen. Wenn ihr jetzt nicht mehr so den Plan habt was das alles zu bedeuten hat, dann zieht
  11. euch das erste Video der Reihe rein. Okay! Wieder zurück zum DEA!
  12. // das dann rauscutten! (ist damit der Frame wieder so ist wie vorher) Ein DEA berechnet also ob ein Wort in einer Sprache liegt.
  13. Der Begriff “Deterministisch” bedeutet hier: Das der Automat nach einer Eingabe nur in einen anderen Zustand wechseln kann.
  14. Einfach gesagt: Dat Ding hat immer nur einen Weg der Fortsetzung. Wir sehen das aber gleich bei einem Beispiel.
  15. Gucken wir uns erstmal an aus was so ein DEA besteht. Formal besteht so ein Deterministischer Automat aus 5 Dingen:
  16. Aus Zuständen Q, diese sind endlich. Aus einem Eingabealphabet, sprich die Menge der erlaubten Eingaben Aus Übergangsfunktionen, die sagen uns wie
  17. wir von einem Zustand in den nächsten kommen Einem Anfangszustand, damit wir auch wissen wo es losgeht und Endzuständen, manchmal gibt es nur einen,
  18. manchmal gibt es auch mehrere. In einfacher *Hust* Kurzschreibweise sieht das ganz dann so aus:
  19. Automat = (Q,Sigma, Delta,q0,F) Ist doch klar und für jeden Verständlich oder? ….Nicht!
  20. Beispiel DEA Übergangsdiagramm Lassen wir den formalen Quatsch mal weg und schauen uns ein Beispiel an.
  21. So Automaten lassen sich am besten mit so genannten Übergangsdiagrammen darstellen. Die roten Bopel sind die ominösen Zustände. In weiß die Pfeile sind die Übergänge.
  22. Man geht also immer wenn eine Bedingung erfüllt ist von einem Zustand in einen anderen über die Pfeile :)
  23. Der erste Zustand ist jetzt mal unser q0 und gleichzeitig der Anfangszustand. Um den Anfangszustand zu markieren, klatscht man so ein Pfeil davor.
  24. Jetzt sagen wir einfach mal: Der nächste Zustand wird mit einem a erreicht. D.h lesen wir ein a kommen wir in den Zustand q1.
  25. Erhalten wir ein b am Anfang, bleiben wir im Anfangszustand. Sind wir in q1 und bekommen ein b, landen wir in q2.
  26. Ist es aber ein a, dann bleiben wir einfach in q1 stehen. Das bedeutet wir können in q1 beliebig viele a’s schreiben, wenn wir so scharf drauf
  27. sind. Sind wir in q2 gelandet und bekommen noch ein b, dann kommen wir in den Zustand q3,
  28. welcher auch der Endzustand ist. Erkennen können wir den Endzustand an zwei Kreisen ineinander.
  29. Sind wir aber in q2 und lesen ein a, gehen wir wieder zurück in q1. Warum?
  30. Weil uns das der Automat so sagt, das ist wie wenn man kurz vor der Schlosstraße bei Monopoly aufeinmal zurück muss und wenn man über Los kommt, darf man keine 2 Millionen
  31. einziehen! - So eine kacke ey. ;D Okay egal zurück zum Thema.
  32. Sind wir in q3 angekommen, können wir dort noch beliebig viele a’s oder b’s lesen und bleiben trotzdem in dem Zustand.
  33. Ah ja und jetzt? Jetzt können wir damit überprüfen ob ein Wort in der Sprache liegt oder nicht.
  34. Wie man unschwer erkennen akzeptiert die Sprache Wörter die aus a’s oder b’s bestehen. Also ist unser Eingabalphabet aus a und b.
  35. Der Stern hinter der Klammer bedeutet, wir können a und b unendlich oft verwenden. Gut dann testen wir doch mal ein bissl rum.
  36. Also nehmen wir mal das Wort: abaabb Los gehts in unserem Anfangszustand q0.
  37. Zuerst liest der Automat jetzt das a. a bedeutet, wir gehen in den Zustand q1. Steht ja auf dem Pfeil.
  38. Dann bekommen wir ein b, ja gut also gehen wir weiter in q2.
  39. Jetzt hauen die uns wieder ein a hin. .Hm nagut dann geh ma halt zurück in q1.
  40. Mit dem nächsten a bleiben wir in q1. Danach bekommen wir noch 2 b’s hintereinander, also gehen wir erst in q2 und von dort aus
  41. in q3. Und sind fertisch!
  42. Am besten ist immer man geht das ganze Wort durch und guckt dann wo man gelandet ist. Wir sind jetzt im Endzustand q3, also ist das Wort abaabb in der Sprache und wird akzeptiert.
  43. Schreibt euch auf: Hat man ein Wort komplett eingelesen und befindet sich dann im Endzustand ist das Wort in der Sprache.
  44. Was gibts noch für Wörter die in der Sprache sind? Zum Beispiel ist auch abba in der Sprache, wer kennt die freshe Gruppe aus den 70ern
  45. noch? ;D Auch abababb ist in der Sprache.
  46. Man erkennt leicht, das man immer zum Endzustand kommt, wenn zwei b’s aufeinanderfolgen. Seht ihr schön im Diagramm: Man braucht sicher zwei b’s hintereinander,
  47. damit man zum Endzustand kommt. Alles was danach kommt ist Teil des Endzustands und somit erlaubt.
  48. Haben wir jetzt ein Wort wie: abababa Landen wir niemals im Endzustand. Somit wird das Wort auch nicht akzeptiert.
  49. Auch abaaab ist nicht in der Sprache. Es wird klar, dass wir immer zwei b’s hintereinander brauchen um in den Endzustand zu kommen.
  50. Zusammengefasst: Wörter die irgendwo 2 b’s hintereinander haben sind drin, der Rest wird nicht akzeptiert.
  51. Klar soweit? Gut! Dann schreibt mal ein paar akzeptierte Wörter in die Kommentare :D
  52. Beispiel DEA Übergangstabelle Eine Möglichkeit so ein DEA darzustellen war also ein Diagramm.
  53. Man kann nen DEA aber auch als Übergangstabelle darstellen! Rechts haben wir euch extra noch mal das Diagramm von gerade eben eingeblendet, damit ihr direkt
  54. Diagramm und Tabelle vergleichen könnt :) Also was kommt in die Tabelle?
  55. In die Spalten kommen die akzeptierten Zeichen, also hier a und b. Und in die Zeilen die jeweiligen Zustände.
  56. Wir starten ja mit dem Zustand q0, also schreiben wir den mit so nem Pfeil davor hin. Dann schauen wir was passiert wenn wir ein a bekommen….
  57. Ja gut wir gehen halt in q1 ne? seht ihr ja auch rechts im Diagramm :) Beim b passiert nix, da bleiben wir beim Zustand q0. Also tragen wir q0 ein :)
  58. Danach schauen wir uns q1 an. Beim a bleiben wir in q1 und beim b gehen wir in q2.
  59. Dasselbe machen wir noch bei q2 und q3. Drückt ruhig Pause und vergleicht Tabelle mit Diagramm. Guckt einfach in welchem Zustand ihr seid und dann guckt in welchen ihr geht wenn ein
  60. a oder ein b kommt :) Da q3 unser Endzustand ist, ballern wir so nen Stern dahinter. Ist halt die Markierung
  61. für Endzustand :) Geil! Jetzt haben wir nen Graphen und eine Tabelle. Die beiden sagen uns genau dasselbe.
  62. Das heißt wir können damit feststellen, ob ein Wort in der Sprache liegt oder nicht. Formal und in einfacher Kurzschreibweise sieht der Automat jetzt übrigens so aus.
  63. Wems gefällt bitte! Aber wir bleiben lieber bei den Übergangsdiagrammen und Tabellen :D
  64. Alright! Was gibt es noch wichtiges zu wissen: Gucken wir uns mal noch paar Besonderheiten an:
  65. Ein DEA besteht meist aus einem Anfangszustand, aber kann mehrere Endzustände besitzen. Der Endzustand kann sich dabei überall im Graphen befinden.
  66. So kann der Endzustand auch gleich der Anfangszustand sein. Wichtig ist: Der DEA kann mit einem Zeichen nur in ein Zustand wechseln
  67. Aber es müssen auch nicht unbedingt alle Zeichen eingelesen werden. Am besten ihr probiert selbst mal aus so ein Ding zu entwerfen.
  68. Zum Beispiel aus dem Alphabet {0,1} und er aktzeptiert nur Wörter, die eine aus der Folge 01 bestehen.
  69. also 0101, oder 010101, usw :) Nice ihr Schlawiner! Dann fassen wir nochmal zusammen:
  70. DEA steht für deterministischer endlicher Automat und ist eine Berechnungsmethode um Wörter einer Sprache erkennen.
  71. Determinismus bedeutet, wir können mit einem Zeichen nur in ein Folgezustand wechseln. Dargestellt werden die Automaten durch einen Übergangsgraphen und/oder eine Überganstabelle.
  72. Dabei wird der Anfangszustand durch ein Pfeil markiert und der Endzustand durch einen Stern bzw im Graphen durch zwei Kreise.
  73. Es kann entweder einen oder mehrere Endzustände geben. Jut damit wisst ihr das DEA nicht nur über die Drug Enforcement Administration bescheid,
  74. sondern auch über Deterministische Endliche Automaten. Wollt ihr noch mehr zu dem Thema wissen, dann schaut auf der Webseite vorbei
  75. Bis dahin macht’s gut! Haut rein und Ciao!

Zum Nachlesen

Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den … Eindeutiger endlicher AutomatDer eindeutige endliche Automat (englisch unambiguous finite automaton, UFA) nimmt seine Stellung zwischen dem deterministischen endlichen Automaten (DEA, engl. Endlicher AutomatEin endlicher Automat (EA, auch Zustandsmaschine, Zustandsautomat; englisch finite state machine, FSM) ist ein Modell eines Verhaltens, bestehend aus … Akzeptor (Informatik)Ein Akzeptor ist in der theoretischen Informatik ein spezieller endlicher Automat. Er zeichnet sich dadurch aus, dass er im Gegensatz zu einem Transduktor …