Formale Sprachen #28 - Kellerautomaten

[@gigi19994]

Dieser Moment wenn du in der Vorlesung verzweifelt da sitzt, und versuchst den Prof zu verstehen. Dann Zuhause vergebens versuchst mit den Folien den Stoff nachzuarbeiten und schon echte Bedenken aufkommen, ob man vielleicht selber einfach zu hohl ist um das Ganze zu verstehen. Dann plötzlich auf deine Videos stößt und alles was der Prof versucht hat in den 2 Std zu erklären, du innerhalb weniger Minuten auf Anhieb so gut verstanden hast, dass du nicht mal mehr beim Lösen einer Aufgabe erstmal nachschlagen musst, wie das alles nochmal war. 😎 Danke vielmals!!

[@lunamoon6146]

Ich hoffe fast, dass wir den gleichen Prof haben... und glaube es auch.

[@gigi19994]

@@lunamoon6146 würde mich nicht wundern😁

[@myzo3050]

Liegt halt daran das der Ehrenmann das so gut erklärt hat

[@RobTain]

Ich schreib bald ne Klausur über diesen Stoff. Ohne deine Videos wäre ich bereits hoffnungslos verloren. Danke dafür!

[@rizzy--]

Ich liebe dich 😂❤️

[@imkeklinkenborg7693]

Ich habe es endlich verstanden. Vielen Dank, super Erklärung! Wir schreiben morgen eine Klausur über NEAs, DEAs und Kellerautomaten, die Kellerautomaten habe ich im Unterricht nie verstanden. Demnach Danke!! :D

[@Andi-oq1xc]

Sachlich einfach, schritt für schritt, einfach perfekt. Danke!

[@galynagrynova84]

das ist mir wirklich sehr gut geholfen:) so gut erklärt wie hier, habe ich nicht gefunden. danke für deine tolle Arbeit! Es bleibt noch die Hoffnung, dass ich die Prüfung bestehe ))Ich begreife es kaum, so wie es uns unterrichtet werden.Unser quasi "außerirdische" Vorlesungsskript verstehe ich nur nach den Videos aus deinem Kanal.

[@Alex-ch3pe]

Irgendwie erinnert mich der Kellerautomat an das Spiel TIS-100... Hmm. Deine Videos sind Top! Unser Skript ist echt für die Tonne, deine Erklärungen hignegen sind super und Idiotensicher.

[@amygdalasologdala6336]

Super gut erklärt....danke 👍

[@NLogSpace]

Randy Welt Das LIFO-Prinzip verwenden wir, damit wir beliebig weit geschachtelte , korrekt geklammerte Ausdrücke erkennen können. Diese kommen an vielen Stellen vor, auch die Syntax der meisten Programmiersprachen basiert darauf. (Denke bei der Sprache im Video bei "a" an eine öffnende Klammer oder ein "begin", bei "b" an eine schließende Klammer oder ein "end".) Die Syntax von Programmiersprachen lassen sich also mittels Kellerautomaten beschreiben, wenn wir das LIFO-Prinzip für den Speicher benutzen, da man immer die Klammer zuerst schließen muss, die zuletzt geöffnet wurde. Über die Frage, was bei einem FIFO-Speicher passieren würde, habe ich noch nie nachgedacht, eine interessante Frage! Ich werde wieder antworten, wenn ich es herausgefunden habe.

[@NLogSpace]

Randy Welt Mit einem FIFO-Speicher würde es sich um einen sogenannten "Queue automaton" handeln, in der englischen Wikipedia gibt es einen Eintrag dazu. Dieses Automatenmodell ist interessanterweise deutlich mächtiger als ein Kellerautomat, und zwar äquivalent zu Turing-Maschinen bzw. Typ-0-Grammatiken.

[@johnbernard5282]

Sehr gut. Genau der richtige schwierigkeitsgrad

[@janikti8605]

Vielen Dank für deine super Hilfe

[@D4lio55]

sehr gutes video, wirklich hilfreich für die klausur morgen :D

[@francescogruen2385]

Richtig gut erklärt, Kompliment!

[@spirosxenerotos828]

danke danke danke

[@JohnnyHRO]

Sehr gute Erklärung des Kellerautomaten. Aber ich hätte eine Frage und zwar kann man einen kellerautomaten in einem Syntaxdiagramm darstellen im Beispiel von Klammerschachtellungen

[@ReddDevil1982]

Prinzip gut erklärt. Rückfrage: Woran erkennst du, dass der von dir gezeigte Kellerautomat Nichtdeterministisch ist? a;A -> AA und epsi;A -> A drück dies den Nichtdeterminimus aus? Wenn ja, warum? Bei ersten lese ich das a, im Keller steht A beim zweiten lese ich epsi (nichts) im Keller steht A

[@Ali-ny4wi]

Like bevor das Video abspielen:)

[@oliveryt7168]

Hilfreiche Zusatzinformationen!

[@luiscosta7316]

Als das erste mal 'b' gelesen wird, wird der ​(ɛ; A->A) übergang benutzt, heißt das also, dass, wenn der Übergang 'b' nicht enthält, der Lesekopf an der gleichen Stelle bleibt?

[@xXPK26realXx]

Danke!

[@farzanehhaidary6622]

Vielen vielen Dank für die gut erklärten Videos! Könnten Sie vielleicht ein Video zur Zeit- und Platzkomplexität machen?

[@NLogSpace]

Ja, Videos zur Komplexität plane ich auch bald zu machen.

[@randywelt8210]

Warum verwenden wir als Speicher ausgerechnet das LIFO Prinzip? Was ist mit dem FIFO Speicher? Zu welcher Grammatik gehört der?

[@bigboss7936]

bester man

[@moustafawafaeibaaj5264]

Super erklärt , ich habe aber klein Frage , wie Unterscheidet man zwichen die Sprachen die im L1 oder L2 sind ? also wie weise ich ob irgendeine Sprache in L1 oder in L2 steht ? pumping lima reicht leider nicht dazu ! Vielen Dank für dein mühe .

[@NLogSpace]

Hi, also wenn eine Sprache in L2 ist, dann kannst Du eine kontextfreie Grammatik oder einen Kellerautomaten angeben. Wenn sie nicht in L2 ist, dann kannst Du versuchen das mit dem Pumping Lemma zu zeigen. Und wenn Du zeigen möchtest, dass sie tatsächlich in L1 liegt, dann kannst Du eine sogenannte monotone Grammatik angeben, zu diesem Thema habe ich auch schon Videos gemacht.

[@moustafawafaeibaaj5264]

Alles klar, danke für die Antwort :)

[@Zwackelmann173]

Turbo nice :D

[@DaevLC]

Du sagst:" Wichtig ist das ein Kellerautomat nicht deterministisch ist"(12:43). Wenn ich Determinismus richtig verstanden habe kann es doch aber auch deterministische Kellerautomaten geben oder? Sollte es nicht eher heißen "ein Kellerautomat muss nicht deterministisch sein" und ist es meistens auch nicht? :D

[@NLogSpace]

Ja, also ich hätte besser sagen sollen: Nichtdeterminismus ist erlaubt. Wenn man Nichtdeterminismus bei Kellerautomaten verbietet, also "deterministische Kellerautomaten" betrachtet, dann können die nicht mehr alle Sprachen erkennen, die ein nichtdeterministischer Kellerautomat erkennen kann. Dies steht im Gegensatz zu DEAs und NEAs, die bekanntlich gleichmächtig sind.

[@tonikaiser2823]

get das auch für kontextsensitive Krammatiken?

[@oliveryt7168]

"Krammatiken".. ist klar.

[@mcari]

Darf man auch mehrere Symbole vom Stack in einem Übergang löschen? Man könnte ja theoretisch auch einfach einen weiteren "Hilfszustand" verwenden, wenn es nicht zulässig wäre, der erst das eine und dann mit einem epsilonübergang das zweite symbol löscht. Aber ist es laut Definition erlaubt, beispielsweise ein a zu lesen und dabei AA -> epsilon zu ersetzen?

[@NLogSpace]

McAri Laut der gewöhnlichen Definition darf man pro Übergang nur ein einziges Symbol vom Stack lesen, aber genau wie du sagst, kann man den allgemeineren Fall mit mehreren Zuständen und Epsilon-Übergängen simulieren.

[@mcari]

Alles klar, danke für die fixe Antwort. Wenn ich die Prüfung bestehe gibts 100€/Meine Note als Spende. Wirklich klasse Videos!

[@NLogSpace]

McAri Haha, na dann drücke ich Dir die Daumen für deine 1.0! ;)

[@DA-rp1wg]

Erstmal Danke für das Video. Muss das Keller nicht leer sein,damit das Wort akzeptiert wird ??

[@NLogSpace]

Es gibt verschiedene Varianten von Kellerautomaten. Bei diesen hier muss der Keller nicht unbedingt leer sein, aber der Automat muss das Wort zu Ende gelesen haben und in einem Endzustand sein.

[@DA-rp1wg]

@@NLogSpace Wie stellt man fest um welche Variante es sich handelt ? Ich schreibe morgen Grundlagen der Informatik Klausur :D

[@mbu8636]

Ich habe das auch aus unserem Skript so verstanden, dass ein Automat in jedem Fall das Wort ganz gelesen haben muss, dann ist aber egal ob er einen Endzustand erreicht hat wenn der Keller leer ist, weil der Automat dann auch nicht weiter kann. Finde Deine Schritt für Schritt Erklärung aber wunderbar, macht vieles wesentlich einfacher verständlich. Warum müssen sich die Profs immer so kompliziert ausdrücken🥸

[@oliveryt7168]

@@mbu8636 bei uns steht, dass der Keller leer sein muss.

[@trashtatur]

Ist man nicht von Anfang an in den ersten beiden Zuständen dank der Kante epsilon; C0 --> C0. Also bei nichts und C0 hat man nen Übergang. Weil du sagst ja das der Übergang erst später passiert ist o_O

[@drublacky1846]

Mit jedem deiner Videos verliert mein Skript etwas von seinem Schrecken 😅

[@ey7004]

Kann mir jmd nichmal zusammenfassen wann Lkel und wann Lautomat gilt?

[@user-ek4ql1xw2o]

Warum darf das letzte b zweimal gelesen werden, wäre das nicht dann ein neues Wort? Also aabbb?

[@jurgenkoslowski2097]

Sehr nuetzliches Video, und ueberhaupt eine huebsche Reihe. Aber ich wuerde gern zwei Ergaenzungen sehen: (0) Wozu braucht man das Kellerendsymbol C_0 wirklich, wenn mit Hilfe von Endzustaenden erkannt werden soll? Wenn es Teil des Kelleralphabets ist, darf man es spaeter erneut auf den Keller schreiben? Wenn nicht, wir der ganze Formalismus sehr unelegant. Was spricht dagegen, den leeren Keller erkennen zu koennen? (1) Es gibt (mindestens) eine zweite Moeglichkeit, Woerter mit einem Kellerautomaten zu erkennen, naemich indem man einen urspruenglich nichtleeren Keller leert; zweckmaessigerweise sollten dann keine Uebergaenge mehr moeglich sein. Auf diese Weise lassen sich kontextfreie Grammatiken direkt in Kellelrautomaten mit nur einem Zustand uebersetzen. (Und im Hinblick auf die Greibach Normalform ist dann auch klar, dass die \eps-Uebergaenge immer eleiminiert werden koennen.) Vielleicht in Nr 29 (hab' ich noch noch nicht gesehen).

[@kahzn]

Tatsächlich wird, wenn man z.B. nach dem Buch von Uwe Schöning ("Theoretische Informatik - kurz gefasst"), lernt, beim Kellerautomaten das Wort dann erkannt, wenn der Keller am Ende leer ist. Das würde auch erklären, warum zu Beginn der Worterkennung unbedingt schon ein Zeichen im Keller vorhanden sein muss. Ich bin mir aber nicht sicher, ob dieser Teil der Lösung im Video dadurch falsch ist oder nicht.

[@a.y5742]

Super video um ins Thema reinzukommen. Wie machst du das bloß mit dem Erklären? Edit: Muss mein Stack leer (bzw c0) sein, damit mein Pfad beim erreichen des Endzustands als erfolgreich gilt?

[@NLogSpace]

Viel Übung und viel über die Sachen nachdenken! Zu der Frage: Es gibt verschiedene Definitionen von Kellerautomaten, die alle die selben Sprachen erzeugen können. In der Definition hier fordere ich nicht, dass der Keller leer oder C0 sein muss, in späteren Videos hingegen manchmal schon.

[@a.y5742]

Okay ich hab hier nämlich eine Aufgabe grade vor mir liegen und es geht mir wie folgt: Wenn ich den Endzustand betrete (aber halt nicht abschliese, noch nicht) hab ich ein c0 im Stack liegen. eine Zulässige eingabe würde bedeuten, dass ich aus c0 ein Epsilon mache(= c0 raus poppen aus dem stack), wenn ich die benötigte Eingabe (die vom Endzustand zum Endzustand zeigt) tätige. Frage ist: darf ich c0 aus dem Stack "rauspoppen" ?

[@NLogSpace]

Ich verstehe die Frage nicht ganz. Aber wenn man einen Übergang von dem Endzustand auf sich selbst macht, der mit "epsilon;C0->epsilon" beschriftet ist, dann kann man, nachdem man das Eingabewort zu Ende gelesen hat und in diesem Zustand landet, auch noch das C0 vom Keller löschen, damit der Keller leer wird.

[@a.y5742]

Danke für die Antwort. Ich bin im Ausdrücken wirklich nicht so gut :D Ich hab die Aufgabe nochmal revue passieren lassen, es blieb mir nichts anderes als c0 aus dem stack rauswerfen zu lassen. Hat gepasst. Ohne dich wär ich nicht so weit gekommen. Du rettest mir quasi das semester in Automaten und Formale sprachen :D

[@f-rosti952]

Töp!