Kellerautomaten
Andreas Schaefer
https://www.youtube.com/watch?v=faYULCjpBtw

Transkript (automatisch erstellt)

0:00 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
0:11 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
0:19 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
0:26 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
0:36 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
0:45 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
0:55 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
1:04 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
1:13 automaten keller automaten weil das eben deren zusätzlicher speicher ist was sie außerdem noch haben ist quasi die endlich kontrolle
1:20 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
1:29 automaten modells die haben ein paar zugeschriebene mit vergleich damit arbeiten können das ganz normal etwas detaillierter an
1:37 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
1:47 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
1:57 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
2:06 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
2:16 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
2:25 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
2:33 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
2:42 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
2:52 nicht determinismus generell haben wir hier bei denen automotive angucken betrachten wir typischerweise nicht deterministisch keller automaten dh sie
3:03 haben die wahl entweder diese eine dieser tradition zu machen oder einen dieser transaktion zu machen man könnte auch deterministische
3:11 angucken allerdings bilden die tatsächlich eine echte teil klasse der nicht deterministisch spielautomaten und die gucken wir hier in dieser in diesen
3:19 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
3:29 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
3:36 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
3:46 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
3:54 müssen und deswegen bleibt dann an dieser stelle hier der keller unverändert wird das was wir rausholen konnten vielleicht wieder rein
4:02 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
4:10 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
4:18 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
4:30 wieder erreicht wenn wir nicht unten angekommen gucken jetzt mal an wie dieser automat dieses wort auch in bwin abarbeiten würde
4:38 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
4:50 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
5:02 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
5:08 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
5:16 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
5:27 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
5:37 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
5:48 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
5:56 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
6:05 komplett abgearbeitet das ist wichtig also das wort darf nicht irgendwie halb abgearbeitet sagt man man ist im endzustand kann nichts mehr tun sondern
6:13 das wort ist wirklich komplett abgearbeitet und wir sind in einem zustand und deswegen akzeptieren wir das wort
6:20 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
6:29 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
6:35 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
6:47 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
6:55 und dann gehen wir nun den zustand und lockern können keller automaten eben zwei an zahlen vergleichen nehmen sie halt werden dass eine
7:04 gesellschaft etwas nicht tun und wenn das andere kommt zum vergleich damit sie daraus gekellnert dass du die grundlegende idee dabei die wird sie
7:11 auch in diesem beispiel schon sehen