Warum können meine Dozenten nicht einfach so erklären... Einfach weniger Fachbegriffe nutzen, die sich eh keiner Merkt, und zack Fertig jeder versteht das Thema. Danke, super verständlich und lebensrettend :)
Geht mir auch so. Und dann in der Klausur nicht abfragen was man sonst gemacht hat sondenr extra die Negation einer Sprache nehmen oder andere Fallen. Ekelhaftes Fach.
Wie verhält es sich, wenn jetzt beim KA nicht alle Zustände von allen Zuständen erreicht werden können? Muss ich dann auch alle Möglichkeiten berücksichtigen? Also zum Beispiel, wenn im obigen Beispiel z.B. es einen weiteren Zustand 2 geben würde, und die Verbindung von 1 zu 2 geht mit Epsilon; C->C, und die Verbindung a; C->epsilon dann von 2 zu 0 statt von 1 zu 0. Dann gibt es ja keine direkte Verbindung von 1 zu 0, und auch keine von 0 zu 2. Müsste man dann irgendwelche Tripel [0,?,2] oder [1,?,0] trotzdem berücksichtigen? (? steht für ein beliebiges Zeichen) Weil egtl. gibt es da ja dann keinen Übergang?
Wenn man einfach alle aufschreibt, egal ob sie möglich sind oder nicht, macht man auf jeden Fall nichts falsch. Man kann auch ein Tripel [i,a,j] weglassen, wenn man den Zustand j von Zustand i aus nicht erreichen kann (auch nicht in mehreren Schritten).
Der Beweis steckt eigentlich in der Tatsache, dass ein Nichtterminal [p,C,q] genau die Worte erzeugen kann, die man auf dem Weg von p nach q lesen kann und dabei das C vom Keller löscht. Für die von Dir gefragte Richtung könnte man mit einem Wort w aus L(G) beginnen. Für dieses gibt es eine Ableitung. Aus dieser Ableitung kann man nun den Lauf des Kellerautomaten konstruieren, da ja jede Grammatik-Regel aufgrund eines bestimmten Übergangs im Kellerautomaten eingeführt wurde. Der Lauf des Kellerautomaten akzeptiert dann ebenfalls w, somit ist w dann auch in L(KA).
Was ist denn wenn ich ein anderes Wort nehme, z.b.: aba. Dann bekomme ich doch eine ganz andere Grammatik heraus. Wie kann man denn nun eine Grammatik erstellen die jedes beliebige Wort des Kellerautomaten akzeptiert? P.S.: Das sind dann wahrscheinlich alle die wir aufgeschrieben haben bei 28:08 oder?
Du hast im Video einen Fall in dem du "[1,D,0]->[1,C,1][1,D,0]..aber zu [1,C,1] gibt es keine Produktionsregeln. Macht das Probleme? Kann/Sollte man das weglassen?
Freut mich, dass Du mich unterstützen möchtest! :) So einen Amazon-Link habe ich leider nicht, sondern nur die Links, die in der Videobeschreibung und auch in der Kanal-Beschreibung stehen.
19:27 Mir wird nicht klar wie z.B. [0, D, 0] --> b [1, D, 0] funktionieren soll: Ich verstehe b [1, D, 0] so, dass von Zustand 1, 'D' beim Übergang zu Zustand 0 gelöscht werden können muss, um die Aufgabe [0, D, 0] zu erfüllen. Von Zustand 1 nach 0 kann aber mangels entsprechender Übergangsfunktion kein D gelöscht werden, was so offensichtlich ist, dass ich hier einen dicken Denkfehler haben muss... Was übersehe ich? 🧐 Die einzige Erklärung die ich habe ist, dass es bei b [1, D, 0] gar nicht darum geht, dass mit dem Übergang von Zustand 1 nach 0 das D gelöscht werden soll, sondern dass irgendwann Zustand 0 erreicht werden und in dem Zuge eben D gelöscht werden soll. Daher dann auch die Schreibweise [0, D, 0] --> b [1, D, 0] Das wiederum heißt, dass mein Denkfehler darin liegt, anzunehmen, dass mit b [1, D, 0] jener verbleibender Zustandsübergang gemeint ist, durch den 'D' gelöscht wird. Kannst du das bestätigen? Und nochmals danke für den enormen Aufwand, den du mit deinen Videos betreibst. Ich schreibe das mittlerweile unter fast jedes Video das ich von dir schaue.
Ja, du hast es quasi selbst beantwortet. Es muss nicht direkt in einem Schritt das D gelöscht werden. [1,D,0] heißt, dass man in Zustand 1 startet und nach irgendeiner Zahl von Schritten in Zustand 0 landet und vom Keller dabei genau das oberste D verschwunden ist. Aber auch hier (wie bei deiner Frage zum anderen Video) ist es so, dass nicht unbedingt alle Regeln der Grammatik überhaupt nötig sind. Aber wenn man alle systematisch hinschreibt, dann hat man nichts falsch gemacht. Ob alle Regeln auch wirklich gebraucht werden ist eine andere Frage.
Ich versteh noch nicht so ganz wieso man aus [0,D,0] -> ...[1,C,1].... bekommen kann. Wir haben doch gar keine Regel um [1,C,1] -> wieder etwas abzuleiten.
Ja, die Grammatik, die man durch diesen Algorithmus erhält, hat möglicherweise überflüssige Regeln. Aber uns interessiert nur, dass sie die richtige Sprache erzeugt.
"Bestimmt so 36 Minuten 20" - sehr präzise geschätzt ;)
"geschätzt" ;)
Das Video ist aber 36:21, also falsch geschätzt, noob!11!!elf!
@@arnoc.2107 ich denke mal @NLogSpace ist Informatiker... somit ist ein Off-By-1 Fehler nicht unüblich ;)
Du erklärst alles sehr verständlich. Vielen Dank, du bist eine große Hilfe für die Klausurvorbereitung!
Du bist der einzige Mensch, der den Algorithmus so klar geklart hat...Ich dachte dass ich sowas nie verstehen werde...Danke!!!!💯
HAMMER! Ich dachte das verstehe ich nie, jetzt das video ca 1 und 1/2 mal angeschaut und es klingt voll machbar!
Vielen Dank!
Vielen Dank für die klaren, hilfreichen Videos!
ich hab deinen Kanal an Kommilitonen empfohlen. Super Erklärung.
Sehr geiles Video, das hilft mir echt weiter! Super erklärt
Hab's geschafft. Das Thema wurde wie immer deutlich und clar erklärt.
Warum können meine Dozenten nicht einfach so erklären... Einfach weniger Fachbegriffe nutzen, die sich eh keiner Merkt, und zack Fertig jeder versteht das Thema. Danke, super verständlich und lebensrettend :)
Geht mir auch so. Und dann in der Klausur nicht abfragen was man sonst gemacht hat sondenr extra die Negation einer Sprache nehmen oder andere Fallen. Ekelhaftes Fach.
Sehr gut erklärt, vielen Dank dir. Daumen hoch!
Gutes Video! Hab heute meine mündliche Prüfung in "Theoretischer Informatik 2". Deine Erklärungen haben mir sehr oft helfen können :p
Vielen Dank, das war wirklich sehr gut erklärt - zumindest diesen Satz aus der Vorlesung für die Prüfung last Minute verstanden!
Sehr gutes Video. Ich schreibe in knapp 2 Wochen Klausuren und dachte ich check die komische Erklärung vom Dozenten nie :)
Super Video :D
Klasse Videoreihe, hilft wirklich sehr :) Wann geht es weiter ?
Danke! Nächste Woche gibt es mal wieder ein Video zu dieser Reihe!
King
Wie verhält es sich, wenn jetzt beim KA nicht alle Zustände von allen Zuständen erreicht werden können? Muss ich dann auch alle Möglichkeiten berücksichtigen?
Also zum Beispiel, wenn im obigen Beispiel z.B. es einen weiteren Zustand 2 geben würde, und die Verbindung von 1 zu 2 geht mit Epsilon; C->C, und die Verbindung a; C->epsilon dann von 2 zu 0 statt von 1 zu 0. Dann gibt es ja keine direkte Verbindung von 1 zu 0, und auch keine von 0 zu 2. Müsste man dann irgendwelche Tripel [0,?,2] oder [1,?,0] trotzdem berücksichtigen? (? steht für ein beliebiges Zeichen) Weil egtl. gibt es da ja dann keinen Übergang?
Wenn man einfach alle aufschreibt, egal ob sie möglich sind oder nicht, macht man auf jeden Fall nichts falsch. Man kann auch ein Tripel [i,a,j] weglassen, wenn man den Zustand j von Zustand i aus nicht erreichen kann (auch nicht in mehreren Schritten).
Eine anschauliche und verständliche Einführung an einem Beispiel.
Gezeigt wird : w in L(KA) dann w in L(G). Fehlt die Umkehrung oder ist das trivial ?
Der Beweis steckt eigentlich in der Tatsache, dass ein Nichtterminal [p,C,q] genau die Worte erzeugen kann, die man auf dem Weg von p nach q lesen kann und dabei das C vom Keller löscht. Für die von Dir gefragte Richtung könnte man mit einem Wort w aus L(G) beginnen. Für dieses gibt es eine Ableitung. Aus dieser Ableitung kann man nun den Lauf des Kellerautomaten konstruieren, da ja jede Grammatik-Regel aufgrund eines bestimmten Übergangs im Kellerautomaten eingeführt wurde. Der Lauf des Kellerautomaten akzeptiert dann ebenfalls w, somit ist w dann auch in L(KA).
Was ist denn wenn ich ein anderes Wort nehme, z.b.: aba. Dann bekomme ich doch eine ganz andere Grammatik heraus. Wie kann man denn nun eine Grammatik erstellen die jedes beliebige Wort des Kellerautomaten akzeptiert? P.S.: Das sind dann wahrscheinlich alle die wir aufgeschrieben haben bei 28:08 oder?
31:40
Beim ab[1, D, 0] [0, C, 0] hast du das [0, C, 0] weggelassen.
Hätte man das bei a[0, D, 0] [0, C, 0] auch machen können?
Ja. Die Regel [0,C,0] -> epsilon können wir jederzeit anwenden.
Du hast im Video einen Fall in dem du "[1,D,0]->[1,C,1][1,D,0]..aber zu [1,C,1] gibt es keine Produktionsregeln. Macht das Probleme? Kann/Sollte man das weglassen?
Ja, wenn es zu einem Nichtterminal A keine Produktionen der Form A -> ... gibt, kann man alle Regeln mit A weglassen, das ändert die Sprache nicht.
Hast du zufällig auch nen Amazon Affiliate Code? Würde deine super Arbeit gerne unterstützen!
Freut mich, dass Du mich unterstützen möchtest! :) So einen Amazon-Link habe ich leider nicht, sondern nur die Links, die in der Videobeschreibung und auch in der Kanal-Beschreibung stehen.
19:27
Mir wird nicht klar wie z.B. [0, D, 0] --> b [1, D, 0] funktionieren soll:
Ich verstehe b [1, D, 0] so, dass von Zustand 1, 'D' beim Übergang zu Zustand 0 gelöscht werden können muss, um die Aufgabe [0, D, 0] zu erfüllen. Von Zustand 1 nach 0 kann aber mangels entsprechender Übergangsfunktion kein D gelöscht werden, was so offensichtlich ist, dass ich hier einen dicken Denkfehler haben muss...
Was übersehe ich? 🧐
Die einzige Erklärung die ich habe ist, dass es bei b [1, D, 0] gar nicht darum geht, dass mit dem Übergang von Zustand 1 nach 0 das D gelöscht werden soll, sondern dass irgendwann Zustand 0 erreicht werden und in dem Zuge eben D gelöscht werden soll. Daher dann auch die Schreibweise [0, D, 0] --> b [1, D, 0]
Das wiederum heißt, dass mein Denkfehler darin liegt, anzunehmen, dass mit b [1, D, 0] jener verbleibender Zustandsübergang gemeint ist, durch den 'D' gelöscht wird.
Kannst du das bestätigen?
Und nochmals danke für den enormen Aufwand, den du mit deinen Videos betreibst. Ich schreibe das mittlerweile unter fast jedes Video das ich von dir schaue.
Ja, du hast es quasi selbst beantwortet. Es muss nicht direkt in einem Schritt das D gelöscht werden. [1,D,0] heißt, dass man in Zustand 1 startet und nach irgendeiner Zahl von Schritten in Zustand 0 landet und vom Keller dabei genau das oberste D verschwunden ist. Aber auch hier (wie bei deiner Frage zum anderen Video) ist es so, dass nicht unbedingt alle Regeln der Grammatik überhaupt nötig sind. Aber wenn man alle systematisch hinschreibt, dann hat man nichts falsch gemacht. Ob alle Regeln auch wirklich gebraucht werden ist eine andere Frage.
Ich versteh noch nicht so ganz wieso man aus [0,D,0] -> ...[1,C,1].... bekommen kann.
Wir haben doch gar keine Regel um [1,C,1] -> wieder etwas abzuleiten.
Ja, die Grammatik, die man durch diesen Algorithmus erhält, hat möglicherweise überflüssige Regeln. Aber uns interessiert nur, dass sie die richtige Sprache erzeugt.
@@NLogSpace ok danke :)
C wie Startzustand...