Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Formale Sprachen #28 - Kellerautomaten
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 98 Zeilen
- so in diesem Video wollen wir ein neues Werkzeug kennenlernen mit dem wir formale Sprachen definieren können wir haben schon eine ganze Menge
- kennengelernt wir hatten die wir hatten die deas die neas dann hatten wir Epsilon neas reguläre Ausdrücke und zuletzt dann noch die kontextfreien
- Grammatiken also das waren fünf Werkzeuge die wir bereits kennengelernt haben jedes von denen z.B irg ein Epsilon näher dann definiert er uns eine
- Sprache ja und jedes von diesen Objekten definiert uns immer eine Sprache also das sind unsere Werkzeuge und diesmal kommt ein neues Werkzeug hzu nämlich die
- sogenannten kellerautomaten und ich möchte am besten gleich beschreiben wo die sich einordnen können wir hatten von diesen vier Werkzeugen gesehen dass sie
- dieselbe sprachklasse uns geben die hatten wir dann mit L3 bezeichnet ja also jeder der oder näher oder EPS näher oder regulärer Ausdruck gibt uns immer
- eine Sprache vom Typ L3 das sind waren die erkennbaren oder auch die regulären Sprachen und die kellerautomaten die können wir dann mit den kontextfreien
- Grammatiken in eine Kategorie stecken denn was die uns geben sind Sprachen aus L2 ja wir hatten gesehen die kontextfreien Sprachen können mehr
- Kfen Grammatiken können mehr als diese vier Werkzeuge hier ja sie konnten sowas wie a hoch n B hoch n erzeugen was die hier nicht konnten und die
- kellerautomaten die werden letztendlich genau dasselbe können aber wie der Name schon sagt das sind jetzt keine Grammatik mehr das sind wieder Automaten
- ja wir haben also jetzt wieder ein Automaten Modell was wir jetzt kennenlernen werden in diesem Video gut dann fangen wir auch gleich an was ist
- ein kellerautomat also erstmal hat er wieder wie ein ganz normaler näher hat er Zustände und Startzustand und Zustandsübergänge und Endzustände ja
- also wieder irgendwie sowas hier in der Art und ich habe jetzt an die Zustandsübergänge noch nichts rangeschrieben weil die sich jetzt
- verändern werden so bevor ich jetzt das genauer sage wie die sich verändern gehen wir erstmal darauf ein warum der kellerautomat heißt das ist nämlich kein
- normaler Automat mehr der hat jetzt auch noch einen Keller und was ist ein Keller ein Keller ist eine speicherstuktur eine Datenstruktur wird auch Stack genannt in
- der Informatik das ist euch vielleicht beim Programmieren schon mal über den Weg gelaufen was ist ein Stack ein Stack ist so eine
- Datenstruktur auf der wir Informationen speichern können und zwar legen wir neue Information immer oben rauf wie auf so ein Stack Stack heißt ja Stapel
- ne und wenn wir auf den Stack zugreifen wollen dann können wir auch immer nur die oberste Information lesen ja also dann haben wir da vielleicht
- irgendwelche Informationen ich bezeichne die mal jetzt mit Großbuchstaben das ist so der Boden ne und wenn wir jetzt einmal auf den sec zugreifen dann können
- wir nur die oberste Information lesen in diesem Fall nur dieses B ja und dann könnten wir in diesem Zugriff vielleicht auch das B
- löschen und wir können irgendwas neues raufschreiben können auch mehrere Symbole raufschreiben z.B mal drei Stück in
- einem Schritt raufschreiben ja können aber nie mehr als eins in einem Schritt lesen ja also wir wenn jetzt der nächste Zugriff kommt wir könnten dieses D hier
- niemals lesen oder alles was da drunter liegt alles was wir lesen können ist das E hier oben ja so funktioniert ein Zugriff auf einen Stack und so ein
- Kellerer Automat der hat halt einen Stack und während er dann so durch den Automaten läuft wird er auch immer gleichzeitig an diesem Stack hier
- irgendwas tun so und was genau oder wie genau das funktioniert das sehen wir uns jetzt an und zwar sind die Zustandsübergänge jetzt nicht mehr nur
- mit Symbolen beschriftet ja nicht mehr nur mit ABC und so weiter sondern an einem Zustandsübergang steht jetzt immer eine Information der folgenden Art da
- steht ein eingabesymbol dann steht da ein Semikolon dann steht da ein kellerersymbol ja also formal gesehen haben wir für den Keller oder für diesen
- Stack auch wieder ein eigenes Alphabet und hier muss dann ein Symbol aus diesem kelleralphabet stehen dann kommt PIL und dann kommt noch ein Wort bestehend aus
- kellersymbolen nämlich das was wir dann raufschreiben auf den Keller ja in jedem Schritt werden wir ein kellersymbol lesen das werden wir löschen und
- stattdessen etwas Neues raufschreiben z.B ein a ja wir könnten aber auch mehrere Symbole raufschreiben können uns auch dafür entscheiden gar
- nichts drauf zu schreiben dann könnte man hier EP hinschreiben wir könnten auch was oben drauf schreiben auf das C das das drückt man so aus z.B AC das
- heißt lösche das C und schreibe stattdessen ca rauf also man liest das hier von hinten nach vorne ja das würde bedeuten wenn da auf dem Keller im
- Moment ein C oben steht und wir kommen zu diesem Übergang dann mach aus diesem C ein ca ja so wie es hier steht ja das ist das was ein was so ein
- Zustandsübergang aussagt und solche Übergänge die werden jetzt hier dran stehen und ich habe schon mal ein Beispiel dafür vorbereitet so hier sehen
- wir gleich mal einen Keller Automaten drei Zustände hier gibt's eine Schleife mit zwei Übergängen ja immer so eine ganze Zeile ist immer ein
- Zustandsübergang ja hier ist auch eine Kante an der zwei Übergänge dran stehen hier noch eine Schleife mit einem Übergang und hier noch ein Übergang so
- und jetzt sind hier noch ein paar Sachen die ich zusätzlich erklären mus und zwar die erste Sache beim kellerautomaten da einigt man sich
- darauf dass am Anfang wenn wir den Automaten betreten also wenn wir hier das erste Mal im Startzustand uns befinden dass dann bereits ein Symbol
- auf dem Keller steht das sogenannte kellerstsymbol das wird meistens mit C0 bezeichnet und die zweite Sache die ich noch erwähnen muss ist dass wir auch
- hier wieder EPS Übergänge zulassen also so wie wir damals bei den S NAS gesehen hatten wir lassen auch wieder zu dass hier vorne ein S steht das bedeutet dass
- wir von unserem eingabewort gar kein Symbol lesen sondern nur abhängig vom Keller irgendwas tun okay gehen wir einfach mal
- jetzt beispielhaft diesen Automaten hier durch was der macht er bekommt erstmal ein eingabewort nehmen wir mal das Wort na mache ich mal bisschen komplizierter
- das Wort aabb das geben wir ihm als eingabewort auf dem Keller steht im Moment oben C0 und wir befinden uns
- jetzt hier in diesem Zustand so was können wir jetzt tun der Lesekopf der steht jetzt auf diesem a hier und unser Keller Lesekopf sozusagen der guckt
- immer nur auf das oberste der sieht das C0 okay wir sehen im eingabeworten a wir sehen im Keller oben ein C0 dann suchen wir uns jetzt einen Zustandsübergang von
- hier aus den wir mit A und C0 gehen dürfen und da kommt nur dieser hier in Frage ja wenn wir wenn wir ein a lesen und ein C0 oben im
- Keller steht dann machen wir folgendes wir gehen wieder in diesen Zustand hier zurück deswegen steht er hier an der Schleife ne sind also wieder in dem
- Zustand danach was ändern wir wir ersetzen das C0 durch ac0 mit anderen Worten es kommt ein a oben rauf ja und wir haben dieses a hier gelesen also
- wandern wir zum nächsten Symbol und auch hier äh wir können das C0 jetzt nicht mehr sehen sondern wir können gleich nur noch das a dort oben sehen so jetzt sind
- wir also wieder in diesem Zustand weil wir in eine Schleife gelaufen sind und wir sind in dieser Situation wir lesen ein A und oben steht auch ein A und ich
- muss sagen ich habe eben eine Sache nicht erwähnt wir hatten hier tatsächlich zwei Möglichkeiten eben schon ja denn diese Epsilon Kanten die
- dürfen wir jederzeit gehen so war das ja bei den n auch wenn da eine Kante ist dann dürfen wir die jederzeit benutzen also
- wenn wir hier sind dürfen wir jederzeit darüber gehen diesmal aber mit der Einschränkung dass natürlich auch noch das kellerersymbol stimmen muss ja in
- diesem Fall kommen in unserem Keller aber nur a und C0 vor ja also immer wenn hier oben ein A oder ein C0 steht dann dürf einfach von hier nach hier rüber
- gehen ohne dass unser Lesekopf hier oben weiter wandert ja wir lesen nichts weiter und könnten einfach darüber gehen ja und diese Option haben wir jetzt auch
- wieder wir befinden uns ja hier könnten jetzt hier rüber gehen und das a im Keller durch ein a ersetzen also mit anderen
- Worten ist einfach unverändert lassen machen wir aber erstmal nicht wir entscheiden uns wieder für den Zustandsübergang hier unten ja wenn wir
- ein klein a lesen im eingabewort und hier ein groß a auf dem Keller steht dann dann können wir diesen Übergang hier benutzen der sagt
- ersetzt das groß a durch zweimal groß a ja also mit anderen Worten wir haben jetzt noch ein a oben rauf geschrieben und dann sind wir fertig wir unsere
- Leseköpfe wandern wieder ein Stück weiter so wir sind immer noch in diesem Zustand diesmal steht unser Lesekopf auf klein B hier auf dem Stack oben steht
- ein a dann können wir keinen von diesen beiden Übergängen hier nehmen denn die können wir nur benutzen wenn wir ein a lesen ja lesen aber ein B das heißt was
- können wir tun wir können stattdessen ein von den EPS übergäng nehmen könnten darüber gehen dürfen wir das auch wirklich machen ja denn hier
- steht ein groß a stimmt auch im Keller ist auch ein groß a das heißt wir gehen diesen über Übergang und ersetzen dabei das große a durch groß a mit anderen
- Worten es passiert gar nichts ja also wir haben hier im eingabewort Nichts weitergelesen wir haben auf dem nichts verändert wir sind einfach hier rüber
- gegangen befinden wir uns hier was gibt es jetzt für Möglichkeiten es gibt hier zwei ausgehende Kanten einmal eine Epson Kante mit C0 beschriftet die
- dürfen wir nicht benutzen denn oben auf dem Keller steht a und nicht C0 können wir diese Kante hier benutzen ja die können wir benutzen denn hier steht
- wir lesen ein B das stimmt und oben auf dem Keller steht ein a das das stimmt auch dann dürfen wir also diese Schleife hier gehen befinden uns also wieder hier
- dabei wandert der Lesekopf jetzt wieder um ein weiter und auf dem Keller löschen wir das a ja hier steht a fil EP das heißt dieses a hier wird ersetzt durch
- EPS mit anderen Worten es verschwindet einfach und dann befindet sich unser Lesekopf für den Keller wieder hier und jetzt können wir das ganze Spiel noch
- mal machen können wieder dieses B hier lesen und gleichzeitig dieses a hier löschen dann sieht das ganze so aus wir sind mit dem Wort fertig ja wir haben
- das letzte Symbol gelesen unser Lesekopf können wir uns vorstellen der steht jetzt hinter dem Wort äh und auf dem Keller steht jetzt auch
- nichts mehr außer unserem 100 und wir befinden uns hier was heißt das wenn wir hier schon angekommen sind eigentlich kann so ein Automat ja dann
- nicht mehr weiterlaufen aber wir haben ja noch epsübergänge ja eponübergänge dürfen wir immer noch machen und tatsächlich gibt es hier den Epsilon
- Übergang wenn im Keller ein C0 steht dann dürfen wir hier rüber gehen ohne noch ein weiteres Symbol zu lesen also wir dürfen jetzt diesen Übergang noch
- machen äh um in den Endzustand zu kommen und was passiert dabei auf dem Keller gar nichts C0 wird durch 100 ersetzt also das bleibt so und was auf dem
- Keller steht ist völlig irrelevant sobald wir einen nendzustand erreicht haben äh und das Wort zu Ende gelesen haben
- ja dann heißt das dass unser Wort akzeptiert wird ganz egal was dann noch auf dem Keller steht der Keller der war nur so ein Hilfsmittel zwischendurch um
- noch mehr Bedingungen an unsere Zustandsübergänge zu stellen ja alsobald wir hier einmal angekommen sind und das Wort fertig gelesen haben sagen wir das
- Wort ist akzeptiert ja und genauso definiert man dann eben die von einem kellerautomaten erkannte Sprache ja das sind alle Wörter bei denen man vom
- Startzustand in einen Endzustand gelangen kann äh s dass man das gesamte Wort dabei liest ja und wie gesagt die ganze Zeit
- immer diese nur diese erlaubten Übergänge macht und immer darauf achtet was mit dem Keller passieren soll ja und wichtig ist hier
- auch wieder dass so ein kellerautomat nicht deterministisch ist ja ich habe ja schon gesagt wenn es einen Pfad gibt der uns dahin führt das heißt
- es kann wieder mehrere fade geben es können auch wieder welche in welche Sackgassen führen wichtig ist nur wenn es einen Pfad gibt ja und wir haben
- gerade gezeigt es gibt so ein Pfad ind dem wir erst zweimal diesen Übergang nehmen dann hier dann zweimal diese Schleife und dann so es gibt ein pfah
- mit dem kommen wir hier am Ende an und haben das Wort fertig gelesen dann ist das Wort in der Sprache ja zum Vergleich noch mal was wäre passiert wenn wir uns
- hier am Anfang anders entschieden hätten wenn wir einen anderen Zustandsübergang genommen hätten also nehmen wir an wir fangen fangen das noch mal an das ganze
- sind hier in diesem Zustand äh das nächste Symbol ist ein a auf dem Keller steht ein C0 und wir entscheiden uns jetzt aber sofort für diesen EPS
- Übergang denn C0 steht oben auf dem Keller hier steht wenn C0 oben auf dem Keller steht dann dürfen wir ein EPS Übergang hier machen nach hierhin und
- auf dem Keller soll wieder ein C0 stehen dann sind wir also hier und es hat sich nichts geändert sonst dann haben wir zwei Möglichkeiten für bestimmte für
- welche Übergänge wir könnten entweder ein B lesen tun wir aber gar nicht hier steht ein a also entfällt schon mal dieser
- Zustandsübergang ja den können wir nur machen wenn da jetzt ein B kommt es kommt aber ein a können aber ein EPS Übergang machen
- und zwar wenn da ein C0 auf dem Keller steht das tut es tatsächlich noch ne steht immer noch ein C0 das heißt wir machen diesen Zustandsübergang
- ersetzen das C0 durch C0 okay da passiert nichts dann befinden wir uns im Endzustand aber wir haben das Wort nicht zu Ende gelesen und es gibt auch keine
- Zustandsübergänge mehr ja das heißt dieser Pfad hat uns nicht zum Ziel gebracht denn das Wort ist nicht zu Ende gelesen worden wichtig ist wirklich
- dass das Wort so dass unser Lesekopf am Ende hier hinten steht wir müssen alle Symbole gelesen haben und dann im Endzustand sein dann war dieser Pfad
- erfolgreich ja dieser Pfad jetzt der war nicht erfolgreich ja es gab aber den anderen erfolgreichen deswegen ist das ganze Wort doch in der Sprache ich hoffe
- damit ist das Prinzip von kellerautomaten K K geworden falls ihr Fragen habt schreibt sie gerne in die Kommentare dann kann ich sie vielleicht
- schon im nächsten Video beantworten bis dann
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.
Nichtdeterministischer endlicher AutomatEin nichtdeterministischer endlicher Automat (NEA; englisch nondeterministic finite automaton, NFA) ist ein endlicher Automat, bei dem es für den …
Kontextfreie SpracheKontextfreie Sprachen werden auch als Typ-2-Sprachen der Chomsky-Hierarchie bezeichnet. Die Klasse aller kontextfreien Sprachen beinhaltet die regulären …