ฝัง
- เผยแพร่เมื่อ 4 ก.ย. 2024
- Wir sehen uns an, wie man eine kontextfreie Grammatik in einen Kellerautomaten umwandelt, welcher die gleiche Sprache erkennt. Dies ist eine Richtung des Beweises der Äquivalenz von Kellerautomaten und kontextfreien Grammatiken.
Du bist jetzt mein Daniel Jung für theoretische Informatik.... Danke Daniel
Ich heiße Leif, aber danke! :)
Wau, toll. Ich habe die Konstruktion des Kellerautomats aus einer Grammatik verstanden. Unglaublich.
Danke Ihnen.
Immer gerne! :)
Immer wieder nice wenn du ein Video hochlädst. Einfach, entspannt und gut erklärt - danke!
Vielen Dank... Super Video um den Beweis in unserer Vorlesung nachzuvollziehen zu können :)
Nachvollziehbare Erklärung. Sehr hilfreich. 👍
Vielen Dank für deine VIdeos !!!
Alles sehr gut erklärt
Bester Mann :)
Super erklärt. Vielen Dank. :)
super videos danke du rettest mir echt den arsch
Danke, hat mir echt den Arsch gerettet
sehr gutes video
bei mir hast du gerade genau 10k abos, glückwunsch!!!
Dankeschön! :)
Vielen Dank für die Videos, retten mir echt den A*sch :P.
Kommt wahrscheinlich zu spät, aber könntest du Videos zum Thema Programmverifikation mit Hoaren-Trippeln und Schleifenverifikation mit Vollständiger Induktion machen? (z.B. Induktion über die Anzahl noch auszuführender Rekursionsschritte/Induktion über Invariantenvariable)
Danke dir!
Kannst du bitte das 7Tupel des Keller Automaten noch angeben?
was ich nicht verstehe:
in unseren Vorlesungsfolien wird ein Kellerautomat so definiert, dass sich das Eingabealphabet Sigma und das Kelleralphabet son komisches r, unterscheiden.
In deiner Konstruktion packst du allerdings einfach solche Eingabesymbole mit auf den Keller. Ist das denn erlaubt? kann man einfach solche Eingabesymbole zum Kelleralphabet hinzufügen?
Gruß
edit. wenn ich drüber nachdenke, dann glaub ich, dass es nicht dramatisch ist, dass ein Symbol doppelt vorkommt, einmal im Eingabealphabet und einmal im Kelleralphabet.
hab jetzt auch das Video ganz fertig geguckt und da erklärst du es ja mit den Verifizierungsregeln.
Vielen Dank für deine guten Uploads :)
Können sie mir vielleicht beantworten wie man erkennt, wann man mehr als nur einen Zustand braucht? Braucht man für kontextfreie Grammatiken immer nur einen Zustand bei Kellerautomaten? Ich muss nämlich einen für die Sprache a^nb^mc^n wobei n,m >= 0 bauen. Habe mir bereits eine Grammatik aufgestellt mit zwei Variablen und würde den jetzt einfach genauso bauen, wie in Ihrem Beispiel. Geht das?
Das Verfahren, das ich in dem Video gezeigt habe, funktioniert für jede kontextfreie Grammatik. Ein Zustand ist also immer ausreichend, wenn Du den Automaten nach diesem Verfahren baust. Aber achte darauf, dass es ein Kellerautomat ist, der per leerem Keller akzeptiert. Es gibt auch Kellerautomaten, die durch akzeptierende Zustände akzeptieren, da bräuchte man dann zwei Zustände.
Wie würden dann die Übergänge zum 2. Zustand aussehen ?
danke! ergibt es dann nicht immer Sinn erstmal eine kontextfreie Grammatik zu entwickeln und dann den Automaten dazu zu zeichnen? Und ist das Entwickeln von einer kontextfreie Grammatik immer nur "logisches Schlussfolgern", gibt es da keine Schritte auf die man achten kann? Freu mich über eine Antwort!
Kontextfreie Grammatiken und Kellerautomaten sind gleich mächtig, man kann also hin und her übersetzen. Man kann also bei jeder Sprache das Modell wählen, das einem einfacher erscheint und das kann auch manchmal der Kellerautomat sein.
Und zum Konstruieren von kontextfreien Grammatiken würde ich sagen: Viel üben und versuchen Beispiele immer bis ins letzte Detail versuchen zu verstehen!
@@NLogSpace wow Danke! Du verschönerst den Gedanken an die Klausur in zwei Wochen ! :D
mist, ist nicht deterministisch... dachte ich hätte die lösung