Eine Überlegung, wie man zu einer gegebenen Sprache einen Kellerautomaten findet, bzw. zwei Möglichkeiten, wie der Automat aussehen kann. Einführung Kellerautomaten: • Theorie: Einführung Ke...
wäre es nicht einfacher gewesen für jedes a, dass du liest zwei A auf den Keller zu schreiben, dann ist die Anzahl A im Keller gleich der Anzahl b, d.h. man muss mit jedem b ein A aus dem Keller löschen und am Ende liest man halt we du richtig sagtest mit epsilon das Kellersysmbol raus
Dachte ich mir auch sofort aber manchmal ist das so, dass einem die komplexeste Lösung einfällt mit 10 Zuständen und ein anderer Student kommt und schreibt das Ergebnis mit zwei Zuständen auf ^^
Hey, erstmal danke für das super Video, ist echt alles sehr verständlich erklärt :) Ich hab eine Frage zum Einlesen aus dem Eingabewort. Könnte man sich nicht die zusätzlichen Zustände und/oder Schleifen sparen, wenn man von q0 nach q1 mit: "bb, A, Epsilon" geht? Oder lässt sich immer nur ein Symbol aus dem Eingabewort gleichzeitig lesen? Vielen Dank schonmal für die Hilfe! :)
Ja, das ist richtig. In dem Moment, wo der Kellerautomat mit # als oberstes Stacksymbol beginnt, könnte er entweder ein a lesen und in q0 bleiben oder er könnte den Übergang nach qF nehmen. Da dem Automaten in der Situation beide Möglichkeiten offen stehen, ist der Automat nicht deterministisch.
Ich habe das so gelöst, in dem ich den Startzustand q0 genannt habe und falls ich ein b lesen ohne das oberste Symbol im Stack ein A ist, habe ich keinen Übergang definiert. Ich habe generell im zustand q0 keinen Übergang definiert beim lesen eines b's. Nach dem ich ein a gelesen habe, habe ich in den Stack AA# geschrieben und bin in den Zustand q1 übergegangen und falls ich da nochmal ein a gelesen habe und das oberste Symbol ein A ist, habe ich AAA in den Stack geschrieben. Falls ich in Zustand q1 b gelesen habe und das oberste Symbol ein A ist, so habe ich das A mit epsilon gelöscht und bin in den Zustand q2 übergegangen. In dem Zustand habe ich keine Übergänge für a's definiert. Wenn ich in q2 ein b lese und das oberste Symbol ein A ist, habe ich das A mit epsilon gelöscht. Wenn ich nun in q2 ein epsilon gelesen habe und das oberste Symbol # ist, habe ich # durch epsilon gelöscht und bin in den Zustand q0 übergegangen. Was denkst du ?
Okay, das ist ein Kellerautomat der mit leerem Stack akzeptiert. Es werden für jedes a so viele As auf den Stack gepackt, wie bs gelesen werden sollen. Die Lösung finde ich gut. Der Übergang von q2 nach q0 zum Löschen des Stacksymbols ist auf dem ersten Blick verwirrend, da es aussieht, als könnte man wieder von vorne mit Lesen beginnen, allerdings ist der Stack nun leer. Da könnte ein flüchtiger Korrektor drauf reinfallen, gefällt mir. :) Der einzige Punkt ist, dass in der Sprache im Video auch das leere Wort enthalten ist. In deiner Auflistung sehe ich keinen Übergang, der erlaubt, vom Startzustand aus das Stacksymbol zu löschen, wenn nichts gelesen werden muss.
Danke für das Video, habe dadurch endlich verstanden wie ich einen KEllerautomaten Konstruiren muss.
wäre es nicht einfacher gewesen für jedes a, dass du liest zwei A auf den Keller zu schreiben, dann ist die Anzahl A im Keller gleich der Anzahl b, d.h. man muss mit jedem b ein A aus dem Keller löschen und am Ende liest man halt we du richtig sagtest mit epsilon das Kellersysmbol raus
+ColdBreathX Klar, gute Idee. :)
Dachte ich mir auch sofort aber manchmal ist das so, dass einem die komplexeste Lösung einfällt mit 10 Zuständen und ein anderer Student kommt und schreibt das Ergebnis mit zwei Zuständen auf ^^
Dachte ich auch, danke für die bestätigung :D
It's magic! Genial!!!
So hab ich das mit den Kellerautomaten endlich auch verstanden!
Hast du super erklärt... dank dir habe ich verstanden, wie man einen Kellerautomaten konstruiert :)
Sehr gut erklärt. Top!
Hey, erstmal danke für das super Video, ist echt alles sehr verständlich erklärt :)
Ich hab eine Frage zum Einlesen aus dem Eingabewort. Könnte man sich nicht die zusätzlichen Zustände und/oder Schleifen sparen, wenn man von q0 nach q1 mit: "bb, A, Epsilon" geht? Oder lässt sich immer nur ein Symbol aus dem Eingabewort gleichzeitig lesen? Vielen Dank schonmal für die Hilfe! :)
danke, sehr verständlich erklärt~
danke, super video !
darf man auch zwei Wörter wieder in den Stack schreiben, also z.b #AA ?
Das sind schon drei Zeichen. ;) Ja, du darfst eine beliebig lange Verkettung aus Stacksymbolen auf den Stack schreiben.
danke
Vielen Dank!
Danke... hast du sehr gut erklärt ^_~
Kann man denn in q0 nicht einfach bei jedem a-Übergang einfach doppelte Anzahl an A' s in den Keller speichern? Also [a, #, AA#] bzw [a, A, AAA]
Ja habs genauso gelöst
Ok, danke. Ich wollte wissen ob es "per Definition" auch so erlaubt ist.
Vielen Dank ! Wurdest abonniert ;)
ich liebe dichhhhhhh!!!!
Der Automat ist nicht deterministisch oder ?
Ja, das ist richtig. In dem Moment, wo der Kellerautomat mit # als oberstes Stacksymbol beginnt, könnte er entweder ein a lesen und in q0 bleiben oder er könnte den Übergang nach qF nehmen. Da dem Automaten in der Situation beide Möglichkeiten offen stehen, ist der Automat nicht deterministisch.
Okay, danke! :)
Thank you, sweety, that was very helpfull.
Ich habe das so gelöst, in dem ich den Startzustand q0 genannt habe und falls ich ein b lesen ohne das oberste Symbol im Stack ein A ist, habe ich keinen Übergang definiert. Ich habe generell im zustand q0 keinen Übergang definiert beim lesen eines b's. Nach dem ich ein a gelesen habe, habe ich in den Stack AA# geschrieben und bin in den Zustand q1 übergegangen und falls ich da nochmal ein a gelesen habe und das oberste Symbol ein A ist, habe ich AAA in den Stack geschrieben. Falls ich in Zustand q1 b gelesen habe und das oberste Symbol ein A ist, so habe ich das A mit epsilon gelöscht und bin in den Zustand q2 übergegangen. In dem Zustand habe ich keine Übergänge für a's definiert. Wenn ich in q2 ein b lese und das oberste Symbol ein A ist, habe ich das A mit epsilon gelöscht. Wenn ich nun in q2 ein epsilon gelesen habe und das oberste Symbol # ist, habe ich # durch epsilon gelöscht und bin in den Zustand q0 übergegangen. Was denkst du ?
Okay, das ist ein Kellerautomat der mit leerem Stack akzeptiert. Es werden für jedes a so viele As auf den Stack gepackt, wie bs gelesen werden sollen. Die Lösung finde ich gut. Der Übergang von q2 nach q0 zum Löschen des Stacksymbols ist auf dem ersten Blick verwirrend, da es aussieht, als könnte man wieder von vorne mit Lesen beginnen, allerdings ist der Stack nun leer. Da könnte ein flüchtiger Korrektor drauf reinfallen, gefällt mir. :) Der einzige Punkt ist, dass in der Sprache im Video auch das leere Wort enthalten ist. In deiner Auflistung sehe ich keinen Übergang, der erlaubt, vom Startzustand aus das Stacksymbol zu löschen, wenn nichts gelesen werden muss.
@@SamyaDaleh Danke :D
dankeeee