Wir klären weitere Details von Kellerautomaten und stellen 2 Varianten von Kellerautomaten vor, die ebenso mächtig sind, wie die zuerst gezeigte Definition.
Dann bin ich mal Erster! ;) Ich hab bisher noch nichts kommentiert, aber ich denke es ist mal an der Zeit. Gestern habe ich an meiner Hochschule Technische Informatik mit dem Hauptthema Formale Sprachen und Automaten geschrieben und deine Videos haben mir echt geholfen, den teils wirren Folien unseres Dozenten etwas Sinn zu entnehmen. Deswegen mal ein Danke schön! Ich denke eine 2,0 ist drin , dank deiner Hilfe ;)
Bei uns in der Uni schreiben wir i.d.R. ein Kellerstart-Symbol im ersten Schritt selbst hinein und bei uns ist es auch möglich, dass wir ein Epsilon im Keller lesen dürfen. Sprich, ohne zu lesen beispielsweise ein Kellersymbol trotzdem pushen können.^^ Euer Modell gefällt mir eigentlich besser. 😉
Hi Der Automat akzeptiert die Sprache a^n b^n | n aus {0,1,2.......} also einschließlich 0.Da der Automat das leere Wort akzeptiert. Oder habe ich das falsch verstanden ? LG
Vielen Dank für die ganzen tollen Videos. Richtig gut gemacht. Ganz am Ende schreibst du, dass nur Wörter a^n b^n erkannt werden. Wäre durch die Epsilon-Übergänge auch das leere Wort möglich, also (a^nb^n)+Epsilon?
Ja, das leere Wort wird auch akzeptiert. Man muss es aber nicht dazuschreiben, da a^0 b^0 das leere Wort ist. (In der Informatik ist es üblich, die 0 zu den natürlichen Zahlen dazuzunehmen.)
Nein, eine solche Regel erlaube ich in meiner Definition nicht. Es muss immer ein Kellersymbol gelesen werden, d.h. direkt nach dem Semikolon darf kein Epsilon stehen. Und selbst wenn ich diese Regel erlauben würde, so hätte das nicht den von dir erwähnten Effekt: Denn wenn man Epsilon von Stack liest und Epsilon schreibt, dann verändert sich gar nichts auf dem Stack. Stattdessen müsste man Regeln der Form Epsilon;X->Epsilon für jedes Kellersymbol X einführen, damit man das oberste Symbol löscht.
Ah, ok. Wenn man die Regel Epsilon;Epsilon -> Epslion hätte, hieße das dann, dass auch wenn der Stack leer ist, man die Eingabe Epsilon machen könnte? Sodass man z.b trotz leeren Stacks (bei einem automaten des Typs Akzeptanz durch Endzustand) könnte man in den Endzustand Wäre das legitim?
könntest du noch erklären wann genau ein Kellerautomat deterministisch ist? (vllt hast du es schon und ich nicht aufgepasstAm besten anhand eines beispiels ^^
Kurz gesagt: Ein Kellerautomat ist deterministisch, wenn er in jeder Situation immer höchstens eine Möglichkeit hat, was er als nächstes tut. Im Detail: Er ist deterministisch, wenn für jeden Zustand z mit jeder Kombination aus einem Eingabesymbol x und einem Kellersymbol C immer höchstens ein Zustandsübergang von z aus existiert, der mit Eigabesymbol x und Kellersymbol C versehen ist, oder alternativ, wenn es in diesem Zustand einen epsilon-Übergang gibt, der mit dem Kellersymbol C versehen ist und dann keine weiteren Übergänge hat, die mit dem Kellersymbol C versehen sind. Es ist schwierig, dies in Worte zu fassen und gleichzeitig die Quantifizierung klar zu machen. Auf Wikipedia gibt es auch eine Beschreibung als Formel, die ist exakter.
Dann bin ich mal Erster! ;) Ich hab bisher noch nichts kommentiert, aber ich denke es ist mal an der Zeit. Gestern habe ich an meiner Hochschule Technische Informatik mit dem Hauptthema Formale Sprachen und Automaten geschrieben und deine Videos haben mir echt geholfen, den teils wirren Folien unseres Dozenten etwas Sinn zu entnehmen. Deswegen mal ein Danke schön! Ich denke eine 2,0 ist drin , dank deiner Hilfe ;)
Sehr schön, das freut mich! :)
Hallo,
beim Leeren der Variante 2 wolltest du wohl schreiben \epsilon; A -> \epsilon ?
Richtig, gut gesehen! :)
Dachte mir auch "Hä? Habe ich das jetzt doch falsch verstanden?".. xD
Bei uns nutzen wir die Variante "Keller soll leer sein, wenn das Wort gelesen wurde"... gut, dass du so eine Ergänzung bringst.
super! Mit dieser Erklärung habe ich es sofort verstanden.
Die Prüfungen für Formale Systeme an der TU Dresden stehen bald an :) vielen Dank für deine Hilfe ^^ du hast vielen Studenten sehr geholfen
kontextsensitive Sprachen, Turingmaschinen und Aussagenlogik hatten wir noch dran ^^ Vielleicht magst du ja auch ein Video dazu machen
blueonification Diese Themen möchte ich auf jeden Fall noch behandeln. Könnte allerdings noch etwas dauern, bis die herauskommen.
bin in der selben situation wie du , nach 7 jahre , an der TU Dresden.. wow
@@mreyas9513 Same, dieser Channel rettet mein Leben
Deine Videos sind super :)
epsi; A -> A muss epsi; A -> epsi sein im neuen Kellerleerungszustand.
Minute 8:31
ja, dachte ich mir auch, dass er was falsch gemacht hat. Sonst sind seine Videos super gut.
Bei uns in der Uni schreiben wir i.d.R. ein Kellerstart-Symbol im ersten Schritt selbst hinein und bei uns ist es auch möglich, dass wir ein Epsilon im Keller lesen dürfen. Sprich, ohne zu lesen beispielsweise ein Kellersymbol trotzdem pushen können.^^ Euer Modell gefällt mir eigentlich besser. 😉
Hi
Der Automat akzeptiert die Sprache a^n b^n | n aus {0,1,2.......}
also einschließlich 0.Da der Automat das leere Wort akzeptiert.
Oder habe ich das falsch verstanden ?
LG
Vielen Dank für die ganzen tollen Videos. Richtig gut gemacht.
Ganz am Ende schreibst du, dass nur Wörter a^n b^n erkannt werden. Wäre durch die Epsilon-Übergänge auch das leere Wort möglich, also (a^nb^n)+Epsilon?
Ja, das leere Wort wird auch akzeptiert. Man muss es aber nicht dazuschreiben, da a^0 b^0 das leere Wort ist. (In der Informatik ist es üblich, die 0 zu den natürlichen Zahlen dazuzunehmen.)
Hieße dann Epsilon;Epsilon -> Epslion: egal was auf dem Stack ist, lösche Lösche das oberste auf dem stack?
Nein, eine solche Regel erlaube ich in meiner Definition nicht. Es muss immer ein Kellersymbol gelesen werden, d.h. direkt nach dem Semikolon darf kein Epsilon stehen. Und selbst wenn ich diese Regel erlauben würde, so hätte das nicht den von dir erwähnten Effekt: Denn wenn man Epsilon von Stack liest und Epsilon schreibt, dann verändert sich gar nichts auf dem Stack. Stattdessen müsste man Regeln der Form Epsilon;X->Epsilon für jedes Kellersymbol X einführen, damit man das oberste Symbol löscht.
Ah, ok. Wenn man die Regel Epsilon;Epsilon -> Epslion hätte, hieße das dann, dass auch wenn der Stack leer ist, man die Eingabe Epsilon machen könnte? Sodass man z.b trotz leeren Stacks (bei einem automaten des Typs Akzeptanz durch Endzustand) könnte man in den Endzustand
Wäre das legitim?
könntest du noch erklären wann genau ein Kellerautomat deterministisch ist? (vllt hast du es schon und ich nicht aufgepasstAm besten anhand eines beispiels ^^
Kurz gesagt: Ein Kellerautomat ist deterministisch, wenn er in jeder Situation immer höchstens eine Möglichkeit hat, was er als nächstes tut.
Im Detail: Er ist deterministisch, wenn für jeden Zustand z mit jeder Kombination aus einem Eingabesymbol x und einem Kellersymbol C immer höchstens ein Zustandsübergang von z aus existiert, der mit Eigabesymbol x und Kellersymbol C versehen ist, oder alternativ, wenn es in diesem Zustand einen epsilon-Übergang gibt, der mit dem Kellersymbol C versehen ist und dann keine weiteren Übergänge hat, die mit dem Kellersymbol C versehen sind.
Es ist schwierig, dies in Worte zu fassen und gleichzeitig die Quantifizierung klar zu machen. Auf Wikipedia gibt es auch eine Beschreibung als Formel, die ist exakter.
danke =)
häää