Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Automatentheorie: Kellerautomaten
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 92 Zeilen
- wir wollen herzlich willkommen zurück zu diesem video wieder im themenbereich der automaten oder heute geht es um die keller automaten warum wir die brauchen
- wir um die gar nicht so uninteressant sind und welche funktionen sie haben und wo ihre grenzen ablegen das gibt es in diesem video los geht's
- [Musik] wir starten das klären wir als erste ist natürlich die frage warum eigentlich der
- keller automat wir haben die dvd deterministischen endlichen automaten dann haben wir jetzt deutlich vereinbarungen erst kennengelernt die
- nicht deterministisch unendlichen automaten die das ganze viel kürzer fassen aber liegen gleichen funktionsumfang hatten und warum
- brauchen wir jetzt im keller automaten und was ist das eigentlich wenn wir mal an wir wollen ein wort bilden mit hoch wären also beliebig viele aaaahs und
- dann genau so viele ps dahinter ja das ist unser ziel wie würde dann das erst mal aussehen veränderte 1 relativ einfach kann ich in automaten bauen er
- in dem fall to 0 wird zu q1 und dann einen weg dann habe ich a b1 b12 kleiner gleich zwei also für 1 und 2 also die worte a b und a bb würde ich
- den automaten so bauen und wir sehen jetzt schon das wird langsam problematischer jetzt will ich aber größer gleich zwei machen jetzt
- habe ich folgendes problem hier dieser automat kann nicht zählen und das ist die sind auch die grenzen der deterministischen endlichen automaten
- sie können nicht zählen drüben müsste ich ja beliebig viele diese zustands paare anhängen um
- erzählen zu können wie viel assist gab und wenn ich jetzt mein ding einen automaten bauen der satz thema ist maximal hintereinander akzeptiert und
- ich würde aber ein wort mit 12 13 14 aus und damit 12 13 14 ps hinterher schreiben dann würde dieser automat das nicht akzeptieren obwohl dieses wort ja
- in unserer sprache unseren akzeptierten eingaben liegen wird das ist also ein problem und das können der es nicht mehr leisten und an dieser stelle kommt der
- keller automat mit seinem keller speicher ins spiel was waren keller speicher und wie funktioniert das haben wir schon von den dynamischen
- datenstrukturen so ein bisschen der keller wird auch als steak bezeichnet was ist das besondere an einen stack das war eine dynamische datenstruktur die
- folgendes prinzip verfolgt nämlich dass last in first out prinzip das was als letztes reingekommen ist geht als erstes wieder raus in dem fall wenn wir die
- folgen abc reinschreiben ja also schreibt unten a b c ja das ziel ist als letztes in unserem keller speicher eingeschrieben worden
- das heißt auch es wird als erstes wieder raus geschrieben ksb dann was a das eba kommt wieder so passt dennoch eigenschaften eines
- keller automaten der keller ist unheimlich groß ja wir können beliebig viele sachen dann abspeichern und wir sehen hier unten schon da
- dieses hashtag oder die alte ist das ende des kellers das kennzeichen oder dieses zeichen kennzahlen wie das ende des kellers das wirst du
- manchmal auch in den anderen zeichen belegt sehen aber wir einigen uns darauf dass das wäre herr staeck ist dann hat der keller drei funktionen und zwar
- einmal die push-funktion die pop funktion und laptop ist eine operation bush ist braucht pushen auf den keller drauflegen und pop ist das oberste
- lehmann rausschmeißen diese drei funktionen gibt es bzw 2 und die keine oft keine funktionen ganz wichtig auch hier wirst du andere modelle eines
- keller automaten kennenlernen gegen ein bisschen anders definiert sind gerade hier auf youtube und existieren ganz viele unterschiedliche ansichten das ist
- eine möglichkeit die möchte ich gerne vorstellen weil sie mit funktionen arbeitet die du nachher auch im dynamischen datenstrukturen nutzen
- kannst es gibt noch andere möglichkeiten lassen sich dadurch aber nicht verwirren ansonsten schreibt gern in die kommentare dann können wir gerne
- jegliche verwirrungen auflösen gehen wir nun weiter wie funktioniert so ein keller automat eigentlich an bord eines kinder im keller automat wird genau dann
- akzeptiert wenn der keller nur noch diesen herr staeck die raute als unterste symbol beinhaltet die eingabe actavis und der automat im
- endzustand mit ist das klingt jetzt nach ganz viel aber es ist eigentlich nur eine sache die dazu kommt was würde in meinem der oder näher gelten eingabe
- abgearbeitet und endzustand beim keller automatik kommt einfach nur noch dahin zu dass der keller leer seinem aus am ende das ist alles also
- haben wir jetzt regeln weil ja schon gelernt der der und der neer unterscheiden sich eigentlich nur durch diese übergangs funktion und wie
- funktioniert das hier regierungsfunktion ist ja ähnlich definiert nur dass wir irgendwie den keller noch mit benutzen müssen das
- heißt wir haben irgendwie einen zustand in dem wir uns befinden das ist cool da haben wir eine eingabe aus dem eingabe alphabet und
- dann haben wir ein zeichen dass ganz oben auf dem keller ist
- das sind unsere drei sachen die auf der linken seite der relation stehen da steht dann auf der rechten seite logisch irgendwie die
- der neue zu also logisch irgendwie der neuen zustand und die aktion die ich auf dem keller ausführen möchte zum beispiel ein paar burschen jetzt
- gucken wir uns jetzt mal ein beispiel an wie das genau aussieht und zwar habe ich mein beispiel kbb ich bin immer noch in meiner sprache
- auch in bebra das wort baby bei der übergangs funktion sieht ja nun folgendes jetzt vor erst mal ganz unten steht der hashtag im keller und ich
- gucke jetzt als erster an dann würde ich ja von cool 0 mit dem a und dem hashtag weil das ja ganz unten
- wieder im tunnel gehen und meine auf den keller schreiben warum schreibe ich meine auf den keller bei in den keller um zu zählen um nachher zu wissen wie
- viele bs muss ich eigentlich schreiben beim zweiten aber genau das gleiche ja ich habe wieder bin weiterhin in ulm
- als eingabe großer um auf dem keller natürlich jetzt bleiben cool und schreiben noch im augen auf jetzt kannst du dich natürlich fragen warum bleiben
- wir den ganzen zeit 0 und gehen nicht in q1 irgendwie weiter meine idee ist stellt es ja kurz vor wir haben cool als staat zustand bleiben solange in kundus
- wir ein baby bekommen dann gehen wir in q1 das heißt hier können wir nur noch bis bekommen und ob wir genügend wie ist bekommen das regeln wir daher über den
- keller jetzt gehen wir zum was macht das b wenn wir in kundl sind und ein b als eingaben gekommen und ein a open auf dem keller ist das ist ganz wichtig dass ein
- oben auf dem keller ist bei sonst haben wir ja entweder schon genügend ausgeschrieben oder es gibt gar keine angst in der eingabe
- danach ist aber auch keine ps geben was machen wir dann wir gehen in q1 weil wir jetzt sagen jetzt in q1 dürfen nur noch b s kommen und warum die pop
- funktion naja mit der ziehen ja sozusagen einen aber wieder ab wir haben ja vorher für jedes a dass wir ins wort geschrieben haben oder in der eingabe
- gelesen haben ein großer auf den keller geschrieben wie jedes große ar müssen wir jetzt ja auch 1b schreiben da wird ja auch ein büro elemente erreichen und
- damit fangen wir sozusagen das zählen an und wir wissen ja dadurch dass das oberste element im keller ein großes jahren muss dass wir auf jeden fall noch
- nicht genügend biss geschrieben haben und die letzte funktion für die rzb ist dann natürlich
- wenn wir in q1 sind bisher was das ist die regel fürs erste b dazu ist die regel wir sind in q1 kommen wochenbeginn eine eingabe es
- steht aber noch nach oben auf dem keller und das ist wirklich wichtig weil sonst wie gesagt haben wir mehr b als a stehen und dann würden wir es wollen nicht mehr
- in der sprache seiner auf ngn also mit dieser funktion wieder die linke 1 bekommen ein b wissen der aroma- und cala sa dann bleiben wir natürlich in q1
- q1 ist der endzustand und meisten wie rhein ahr aus das ist auch schon alles was man jetzt machen könnte weiter gehen will wenn wir in q1 sind
- wenn wir den übergang machen aber nur in dem fall wo ein hashtag im keller steht also das oberste element ist das grundelement sozusagen wenn das der fall
- ist dann gehen wir in q2 was dann unser endzustand ist und dann nutzen wir noch mal die neue operation weil wir nichts mehr machen wollte gucken uns das ganze
- mal normal definiert an eine formale definition des keller oder machen wir wieder über die zustandes menge das kennen wir schon das eingabegerät das
- können wir auch schon nun kommt zum eingabe alphabet noch ein weiteres alphabet nämlich dass keller alphabet ist auch wieder eine nicht lehrer
- endliche menge von zeichen da gibt es einen anfangs symbol im keller bei uns herrschte dieses zeichen ist natürlich teil des
- kellers ganz wichtig dann gibt es eine übergangsform aktion die ist ein bisschen anders definiert wir haben jetzt wieder einen zustand kombiniert
- mit einem zeichen aus dem eingabe alphabet kombiniert mit einem zeichen aus dem keller alphabet wird zu zustand also der neue zustand und eine funktion
- auf dem keller push pop oder rock operation ja eine der drei katar punktion am weiter in einen staat zustand und haben beide eine menge der
- akzeptierten and zustände nehmen sie mal muss natürlich eine teilmenge von puzzeln ganz oben mehr zustande und dann haben wir auch schon die formale
- definition er ist keller beispiel für auch ein buch als normale definition ist keller automaten sehe dann zum beispiel so aus
- wir haben ich habe zwischen jetzt nicht mit cool 0,12 bezeichnen sondern mal mit z06 co2 dann sieht es wie folgt aus 1 0 2
- und b als eingabe weil wir auch ein bio renault wollen anders keller alphabet da brauchen wir auf jeden fall immer erstellt und das große haben wir immer
- für jedes kleine art darauf geschrieben und werden z 2 cent zustand und haben wir eine tabelle die sozusagen uns wäre übergängen definiert wichtig ist eine
- kombination aus eingabe und alter zustand und keller sacken wird zu neuen zustand um eine kombination aus dem alten zustand der eingabe keller zeichen
- willst du ganz rechts genaue zustand unter keller operation also die ersten drei spalten beschreiben sie das was wir eingeben und das die letzten zwei
- spalten beschreiben behindern so und der automat sehe dann auch zum beispiel so aus jahren unsere zu stellen 02 12
- und übergänge wenn wir da und hashtag bekommen pushen wir wenn wir also wenn wir kleine lesen ein großer ast auf dem keller dann prüfen
- wir noch mal drauf und bleiben immer noch in cent 0 und sobald ihr ein belesen und ein großer auf dem keller ganz oben steht schmeißt wäre ein
- grosser runter von den keller und gehen in zell 1 zu machen wir weiter weiter weiter nämlich in z1 noch immer wenn wir ein baby bekommen und ein großer steht
- auf dem keller dann schmeißen wir einfach mal wieder runter und wenn wir fertig sind wieder eingabe und wir in einem nur noch das hashtag
- sozusagen oder die raute unserem keller oder in unserem keller haben dann gehen wir mit einem eps idol übergang der ja bei denen nicht die die
- minister schon ehrlichen automaten existiert also auch empfehle automaten mit einem automatischen übergang in den endzustand co2 aber machen keine
- operation auf dem keller so könnte man den keller automaten definieren man könnte auch tatsächlich die letzten übergang und z2 weglassen jetzt also
- minimal an der stelle aber darum geht es gar nicht so kann man auch mal sehen wie die anwendung eines apps übergangs funktioniert und wir haben sozusagen ein
- ganz klar herausgestellten endzustand 2 mal zusammen was ist ein keller automat der kann sich gelesene zeichen mehr
- der funktioniert nach dem niveau last in first out prinzip im keller können beliebig viele zeichen stehen das heißt dieser keller ist
- unendlich groß ganz unten im keller derby bezeichnet und unser bezeichnet uns das ende regeln denn so definiert das ist der alte zustand mit dem eingabe
- zeichen aus dem eingabe alphabet mit dem keller zeichen oder zeichen auf oben auf dem keller aus dem keller alphabet wird zu den neuen zustand und einer operation
- auf dem keller push pop und naja ein wort nicht nur dann in der sprache was der kein automat akzeptiert wenn der keller nur noch haut enthält
- also im endeffekt leer ist in einem zustand ist und die eingabe abgearbeitet das sind so die sachen die man sich von einem keller automat merken sollte im
- endeffekt ist nichts groß neu ist bis auch dass wir einen der beziehungsweise näher haben mit so einem kleinen extra und das ist der kern
- okay aber wo sind denn dann jetzt noch grenzen für den kenner automaten ist natürlich die frage ja nie erzählen können wir das ist ja alles wunderbar
- das heißt solche worte wie auch ein bohren wenn wir jetzt problemlos mit dem keller automaten überprüfen und natürlich auf weitere
- nichtsdestotrotz gibt es auch für den keller automaten wieder grenzen und du solltest du auch kennen es ist sehr wichtig zum beispiel dieses wort auch
- wenn der nc hoch n können wir nicht wir müssen erstmal mit einem keller machen hast du noch fragen zu keller automaten oder anderen themen in der
- europa league dann schreib mir gerne an freue ich mich wenn wir uns im nächsten video wiedersehen bis dann [Musik]
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.
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 …