Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
PDA - Pushdown Automaton - Automaten & Formale Sprachen 13
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 78 Zeilen
- Pda ? Na da denkt ihr doch bestimmt auch gleich an Periduralanästhesie, ihr Halodris!
- Ehm…. nicht? Ouh jetzt hab ich euch!
- Dann denkt ihr bestimmt an pushdown automaton. Auf Deutsch Kellerautomat.
- Und genau den schauen wir uns jetzt an! So, ihr kennt ja jetzt schon NEAs und DEAs.
- Warum brauchen wir jetzt noch nen PDA? Der große Nachteil von NEAs und DEAs ist, dass sie keinen Speicher haben.
- Die merken sich also nicht,mit welchen Zeichen sie in nen Zustand gelangt sind. Gehen wir mal von nem einfachen Beispiel aus.
- Wir brauchen jetzt nen Automaten, der alle Wörter der Sprache a hoch n , b hoch n erkennt. N ist dabei größer als 0.
- Für n < 2 ohne 0 wäre ein Automat ganz einfach zu zeichnen. Aber was ist, wenn n jetzt immer größer wird?
- Der Automat müsste unendlich fortgesetzt werden. Und das geht natürlich nicht.
- Genau da kommen PDAs zum Einsatz! PDAs verfügen über einen Keller, deswegen auch Kellerautomat.
- Für die Englischsprachigen unter euch, ein Stack. In einem Keller werden Zeichen reingepackt, die sich der Automat merkt.
- Wichtig dabei ist, dass der Keller nach dem Last In - First Out , kurz LIFO, Prinzip funktioniert. Es kann also immer nur das Zeichen rausgenommen werden, welches ganz oben im Keller liegt.
- Also als letztes hinzugefügt wurde. Legen wir mal zum Beispiel A,B und C in den Keller.
- Beim Lesen müssen wir dann zuerst C rausnehmen, dann B und
- dann A. Wir können jetzt nicht zuerst das B rauslesen, bevor wir C rausnehmen.
- Klaro? Der Keller ist hierbei unendlich groß, kann also beliebig viele Zeichen speichern.
- Außerdem steht ganz unten im Keller immer eine Raute. Wenn wir die Raute lesen, wissen wir also,dass wir am Ende des Kellers angekommen sind und
- keine anderen Zeichen mehr drinstehen. Aber wie funktioniert so ein Kellerautomat jetzt?
- Durch den Kellerautomaten wollen wir ja jetzt erkennen ob Wörter in der Sprache liegen. Ein Wort liegt genau dann in der Sprache, wenn der Keller leer und das Wort abgearbeitet
- ist. Ein PDA kann mehrere verschiedene Verarbeitungsschritte haben.
- Links vom Pfeil stehen dabei drei Werte. Der Zustand wo man drin ist, das gelesene Zeichen aus dem Wort und das gelesene Zeichen
- aus dem Keller. Wir sind jetzt zum Beispiel im Zustand q0, lesen im Wort als nächstes ein a und oben
- im Stack liegt ein großes A, welches wir rausnehmen. Rechts vom Pfeil stehen zwei Werte.
- Der Zustand wo man hin will und die Zeichen welche man in den Stack schreiben will. Wir wollen jetzt also in den Zustand q1 und für das rausgenommene große A ein großes
- B auf den Stack legen. Noice!
- Damit das verständlicher ist, springen wir gleich in die Praxis! Machen wir mal ein einfaches Beispiel
- Gehen wir mal von unserer vorhin erwähnten Sprache aus. Wir sollen jetzt nen PDA angeben, der alle Wörter der Sprache erkennt.
- Dafür betrachten wir mal das Wort aabb welches in der Sprache steckt. Wie gehen wir da vor?
- Erstmal überlegen wir uns, dass wir ja immer die gleiche Anzahl an as und bs haben. Also könnten wir, wenn wir ein a lesen was auf den Stack schreiben
- und wenn wir ein b lesen etwas vom Stack wegnehmen. Als erstes schreiben wir aber erstmal nen Zustand q0.
- Dann lesen wir natürlich das erste Zeichen des Wortes, also a. Da zu Beginn ja nur die Raute im Stack liegt, können wir im ersten Schritt ja nur die Raute
- lesen. Somit wäre der Stack jetzt leer.
- Wenn wir das jetzt alles gemacht haben, überlegen wir uns was wir in den Stack schreiben. Sagen wir einfach, dass wir im Zustand q0 bleiben und ein großes A in den Stack hauen.
- Dahinter kommt jetzt noch ne Raute, da wir die ja auch wieder in den Stack hauen wollen. Somit wir das erste a gelesen, die Raute aus dem Stack genommen und durch eine Raute und
- ein großes A ersetzt. Als nächstes sind wir dann wieder im Zustand q0.
- Das nächste gelesene Zeichen ist wieder ein a. Jetzt liegt aber ein großes A ganz oben im Keller, also müssen wir das lesen.
- Wir bleiben jetzt wieder im Zustand q0. Für das gelesene große A schreiben wir jetzt zwei große As, da wir eins ja rausgenommen
- haben aber für unser kleines a auch wieder eins draufhauen wollen. Dann gehen wir weiter.
- Wir sind in Zustand q0 und lesen ein b. Auf dem Stack liegt ein großes A.
- Jetzt gehen wir aber in nen Zustand q1. Den brauchen wir, damit nach der aabb Folge nicht nochmal ein a kommen kann.
- Für das gelesene große A wollen wir jetzt kein Zeichen nachlegen, da wird ja die großen As mit den bs abarbeiten wollen.
- Jetzt sind wir in Zustand q1 und das nächste Zeichen ist ein b. Im Stack liegt jetzt noch ein großes A.
- Wir bleiben jetzt im Zustand q1 und legen kein Zeichen nach. So, jetzt liegt noch die Raute im Keller.
- Wir sind jetzt im Zustand q1. Wir lesen jetzt kein Zeichen, da wir das Wort ja schon abgearbeitet haben.
- Vom Keller nehmen wir jetzt die Raute raus. Dann gehen wir in unseren Endzustand q2 über, da der Keller leer ist und das Wort abgearbeitet
- ist. In den Keller legen wir natürlich nix mehr.
- Und schon is der PDA fertig! Unser PDA erlaubt jetzt alle Wörter die in der Sprache a hoch n , b hoch n liegen, wobei
- n größer 0 ist. Schreibt euch den PDA ruhig auf und überprüft Wörter die in der Sprache liegen, aber auch
- Wörter die nicht in der Sprache liegen. Bei Wörtern die nicht drin liegen wird der Stack nicht leer werden oder aber das Wort
- wird nicht komplett abgearbeitet. Bei einem PDA müsst ihr euch also auf jeden Fall vorher immer überlegen was ihr in den
- Stack schreiben wollt und was ihr dann wieder rausnehmen wollt. Ihr werdet wahrscheinlich viele Ideen brauchen und auch viel ausprobieren aber am Schluss
- sollte es laufen! Ein PDA kann jetzt natürlich auch als Diagramm beschrieben werden.
- Des sieht aber ein bisschen umständlicher aus als beim NEA und DEA. Dabei wird für jeden Schritt geschaut, welche Zustände es gibt und was wir in dem Schritt
- genau machen. Gehen wir mal von folgendem Schritt aus.
- In unserem Schritt steht ein q0. Das heißt wir zeichnen schonmal nen Zustand q0.
- Rechts vom Pfeil sehen wir, dass wir in den Zustand q1 wollen. Also zeichnen wir ne Verbindung von q0 zu nem Zustand q1.
- Jetzt schauen wir wieder Links. Da wir durch das Lesen von a und das rausnehmen von der Raute weiterkommen, zeichnen wir die
- beiden an die Verbindung hin. Dahinter kommen dann noch die beiden Bs und die Raute , da wir das ja dann in den Keller
- reinschreiben wollen. Die Vorgehensweise macht ihr jetzt für jeden Schritt, bis alle Schritte im Diagramm eingezeichnet
- wurden. Und fertisch is das Diagramm zum PDA.
- Na das klingt doch alles logisch. Also dann , tschö!
- Naja oke, so logisch is das doch noch nicht. Schauen wirs uns das Diagramm lieber an nem Beispiel an!
- Gehen wir doch jetzt von unserem vorhin entworfenen PDA aus. Auf unser Diagramm kommen wir jetzt, wenn wir jeden Schritt wie vorhin erklärt aufzeichnen.
- Das sähe dann so aus. Wir haben jetzt unsere drei Zustände q0,q1 und q2.
- Die Übergänge sind die gleichen wie in den Schritten. q2 ist dabei außerdem unser Endzustand.
- Das seht ihr entweder während ihr den PDA aufbaut oder aber es steht in der Aufgabe. Und schon ist das Diagramm zum PDA auch fertisch!
- Tolle Knolle! Was merkt ihr euch jetzt alles zum PDA.
- Ein PDA kann sich , im Gegensatz zum DEA und NEA, die gelesenen Zeichen des Wortes merken. Das macht er mit einem Keller oder Stack.
- Ein Keller funktioniert nach dem Last In - First Out Prinzip. Es kann also nur das Zeichen zuerst aus dem Keller genommen werden, welches als letztes
- hinzugefügt wurde, bzw. im Keller ganz oben liegt. Dem Keller können beliebig viele Zeichen hinzugefügt werden.
- Ganz unten steht eine Raute, um zu erkennen, ob wir am Ende angelangt sind. Ein PDA besteht aus mehreren Schritten.
- Links vom Pfeil stehen dabei drei Werte. Der Zustand wo man drin ist, das gelesene Zeichen aus dem Wort und das gelesene Zeichen
- aus dem Keller. Rechts vom Pfeil stehen zwei Werte.
- Der Zustand wo man hin will und die Zeichen welche man in den Stack schreiben will. Außerdem liegt ein Wort nur in der Sprache, wenn der Stack dann leer ist und das ganze
- Wort abgearbeitet wurde. Um einen PDA als Diagramm darzustellen, müssen wir einfach jeden Schritt durchgehen und die
- jeweiligen Zustände und Werte aufschreiben. So, dat wars zum PDA.
- Hoffentlich war des jetzt soweit verständlich. Ich hau mich ne Runde aufs Ohr.
- Guads nächtle!
Zum Nachlesen
KellerautomatEin Kellerautomat (KA, auch PDA für englisch pushdown automaton; auch Stackmaschine) ist ein Automat im Sinne der theoretischen Informatik, ein Konstrukt, …
Automat (Informatik)Ein Automat oder eine abstrakte Maschine ist in der Informatik, speziell in der Automatentheorie, das Modell eines digitalen, zeitdiskreten Rechners.
ZweikellerautomatDer Begriff Zweikellerautomat (TPDA – engl. Two-stack Push Down Automaton) steht in der Theoretischen Informatik für ein besonderes Automatenmodell.
Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den …