Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Kellerautomaten
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 49 Zeilen
- in diesem video geht es um die keller automaten als automaten modell das zu den kontext freien sprachen gehört werden wir gesehen dass die endlichen
- automaten nicht in der lage sind so eine sprache wie auch zu akzeptieren und da war die intuitive idee einfach dass die endlichen automaten nicht
- zählen können wir haben keinen externen speicher auf dem sich etwas merken können die müssen sich alles im zustand merken und damit
- können sie eben nicht beliebig hoch zählen und dass die idee deswegen sie auch in bochum nicht akzeptieren können und das auch die idee die jetzt zu
- dieser erweiterung führt und die erweiterung sieht so aus dass wir unsere automaten modell mit einem speicher erweitern und der speicher dass es der
- hier das ist jetzt ein stack und dieser stick heißt auch auf deutsch keller speicher und die idee war er seinen stack oder im keller ist ja dass man
- immer noch was drauflegen kann und immer nur das oberste element wieder rausbekommen kann also dass es so einen last in first out prinzip das letzte was
- ich rein tour ist das erste was ich herausbekomme ist beim bücherstapel genauso wie bei einem keller in dem man alles rein stopft deswegen heißt mehr
- automaten keller automaten weil das eben deren zusätzlicher speicher ist was sie außerdem noch haben ist quasi die endlich kontrolle
- die sehr ähnlich zu dem aussieht wie das was wir schon von endlichen automaten erkennen und die die eingabe hier unten dies tatsächlich nicht teil des
- automaten modells die haben ein paar zugeschriebene mit vergleich damit arbeiten können das ganz normal etwas detaillierter an
- bei unserer endlichen kontrolle haben wir natürlich zustände einer der zustände ist der staat zustand hier wir können in zustände haben akzeptieren
- die zustände um weiter zu akzeptieren wir haben eben den stack und das eingabe wort interessant wird es jetzt wenn wir uns die traditionen angucken und bei den
- traditionen ist es so dass diese traditionen immer folgendes tun die können lesen ein zeichen aus der eingabe so wie hier der liest jetzt bei dieser
- tradition dass aus der eingabe der holt das oberste keller symbol aus dem keller raus oder symbole aus gekümmert und angeguckt und wenn das
- einer ist dann kann man eben diese traditionen nehmen also eine pop operation und was sie danach tot ist wenn die traktion genommen wird dann
- wird statt des mahls statt des raus holten symbols wird das eingekehrt was rechts davon steht also in dem falle 21 das heißt der effekt ist dass wir hier
- einen push haben dennoch ein hinzufügt zu dem was vorher schon da war also ein a hinter ist ein arm er im stack als vorher
- das ist die idee bei dieser transaktion es gibt auch traditionen die kein zeichen aus der eingabe lesen y tradition und dadurch bekommt man auch
- nicht determinismus generell haben wir hier bei denen automotive angucken betrachten wir typischerweise nicht deterministisch keller automaten dh sie
- haben die wahl entweder diese eine dieser tradition zu machen oder einen dieser transaktion zu machen man könnte auch deterministische
- angucken allerdings bilden die tatsächlich eine echte teil klasse der nicht deterministisch spielautomaten und die gucken wir hier in dieser in diesen
- kurs nicht an eine weitere möglichkeit ist dass wir einfach nichts wieder ein kellern also das dann so nachricht einfach nur ein aus kellern
- das passiert zum beispiel bei dieser tradition hier da ist es so da wird einfach das haus gekümmert weil das kommt hier raus und wir durch ein eps
- von ersetzt deswegen ist das ein ausgelassen also ein eine kooperation und wenn wir am ende den keller unverändert lassen wollen so wie bei
- dieser tradition hier dann müssen wir einfach das was wir rausgeholt haben hier an der stelle das ist das was wir für ein kellern
- müssen und deswegen bleibt dann an dieser stelle hier der keller unverändert wird das was wir rausholen konnten vielleicht wieder rein
- eine wichtige besonderheit die man hier schon so ein bisschen sieht ist dass wir keine schritte haben die etwas machen wir nichts im keller ist also es ist
- nicht erlaubt irgendwie einen schritt zu machen wenn der keller schon er ist das geht nicht und deswegen benutzt man um zu erkennen dass der
- keller quasi leer ist benutzt man so einen speziellen boden marca das ist hier in dem fall z 0 genannt damit man sehen kann man ist quasi der boden marke
- wieder erreicht wenn wir nicht unten angekommen gucken jetzt mal an wie dieser automat dieses wort auch in bwin abarbeiten würde
- und das läuft einfach so wir sind sozial im staat zustand dann lesen wir dass a und pushen dann eine auf den stack das machen wir einfach mit dieser tradition
- hier die liest jan aus der eingabe z 0 war obendrauf das bedeutet verfügung az 0 dem stack hinzu und das ist genau das was wir im stack haben dann lesen wir
- noch ein a 1 jetzt nehme die zweite transaktion weil jetzt gehe ich ja schon groß aber oben auf dem stick das kommt runter und wird
- durch zwei ersetzt das heißt einnahmen herein das heißt hier haben jetzt zwei es auf dem stack jetzt raten wir dass wir quasi
- die worte haben wechseln den zustand im zweiten zustand werden die erst wieder vom stack getoppt das heißt für jedes b was für ein lesen wird ein affront
- das heißt der ersten schritt und mir das erste herunter und danach haben wir das zweite abstieg runter und haben dabei jeweils die bs gelesen
- jetzt sind wir an der stelle mit der eingabe komplett durch das gut und wir können jetzt die y tradition nehmen weil wir an der stelle den boden marca
- wiedersehen also das sind 0 wir sehen dass der dass wir das wiesenboden marke erreicht haben dass wir also so viele ps gesehen haben wie
- wir vorher hatten ist das also genau zusammenpasst und dann gehen wir in den endzustand ohne den keller zu verändern und jetzt an der stelle haben das wort
- komplett abgearbeitet das ist wichtig also das wort darf nicht irgendwie halb abgearbeitet sagt man man ist im endzustand kann nichts mehr tun sondern
- das wort ist wirklich komplett abgearbeitet und wir sind in einem zustand und deswegen akzeptieren wir das wort
- fassen wir die idee bei der konstruktion noch mal zusammen idee ist in dem ersten zustand wird ein verfehltes aus der eingabe großartige kellert dann machen
- wir quasi eine art strich auf dem keller fehle es an was wir sehen dann entscheiden wir uns irgendwann nicht deterministisch dass wir die mitte
- das in der mitte sind und fangen dann an das was wir eingeführt haben und dieses b was noch also dieser arzt oder im keller haben gegen die b es in der
- eingabe zu menschen also für das was kommt keiner mehr einer aus und wenn wir dann am ende den boden marca sehen dann wissen wir dass die anzahl gleich war
- und dann gehen wir nun den zustand und lockern können keller automaten eben zwei an zahlen vergleichen nehmen sie halt werden dass eine
- gesellschaft etwas nicht tun und wenn das andere kommt zum vergleich damit sie daraus gekellnert dass du die grundlegende idee dabei die wird sie
- auch in diesem beispiel schon sehen
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 …