Theoretische Informatik - Minimierung von DEAs
Вставка
- Опубліковано 27 кві 2017
- Die Komplexität eines deterministischen endlichen Automaten hängt von der Zahl der Zustände ab. Es wird gezeigt, wie zu einem DEA ein äquivalenter DEA mit minimaler Zustandszahl konstruiert werden kann.
Zum Wiederholen extrem gut, vielen Dank das es öffentlich ist.
Wirklich sehr gut erklärt!!!
Super erklärt Dankeschön
Super Video! Grüße von DHBW Mannheim.
Beautiful, jetzt hab ich's gescheckt! Danke!
Ich hab dieses video besser verstanden als meine eigenen folien
Was ist wenn im 2. Schritt Das Grüne Feld eines von den ausgegrauten Feldern ist. Wird dann auch ein (*) gemacht oder nur, falls das Grüne Feld ein (*) ist?
Ein sehr gutes Video vom Inhalt und Qualität.
Great explanation. This is surprisingly easy, even with more complex automata. Thanks for creating :)
Sehr gut erklärt! Danke!
danke sehr gut erklärt
Super erklärt, danke!
Danke
Was ist wenn im 2. Schritt Das Grüne Feld eines von den ausgegrauten Feldern ist. Wird dann auch ein (*) gemacht oder nur, falls das Grüne Feld ein (*) ist?
Wie heißt der Minimierungsalgorithmus, der hier verwendet wird?
Hallo, bin ich im Fach "Theoretische Informatik" stecken geblieben. Ich bräuchte Hilfe bei DEAs/NEAs/Kellerautomaten und Turingmaschinen d.h. jemand, der Coach ist oder Nachhilfe im Bereich gibt? (Die Theorie habe ich viele Male durchgearbeitet, brauche aber Übungen und jemanden zur Seite, um zu sehen was ich falsche mache). An wen könnte ich mich da am besten wenden?
Danke!
Kann man den Algorithmus als beweis für minimalautomaten verwenden?
Sehr gute Erklärung!!
Danke :)
Super!
Was ist wenn im 2. Schritt Das Grüne Feld eines von den ausgegrauten Feldern ist. Wird dann auch ein (*) gemacht oder nur, falls das Grüne Feld ein (*) ist?
Das grüne Feld kann kein graues Feld sein. Wenn es ein graues Feld ist, gibt es eins mit gleicher Beschriftung nicht ausgegraut. Das graue Feld oben rechts z.B. steht für die Menge {q1,q3} und für diese Menge gibt es aber in der zweiten Spalte ein nicht-graues Feld. Die Idee bei dieser Matrix ist, sie so aufzuschreiben, dass es für jede Menge aus zwei unterschiedlichen Zuständen genau ein Feld gibt.
An sich sehr Hilfreich, danke dafür, jedoch finde ich , dass ein wenig zu schnell reden und es einem das mtverfolgen etwas schwer macht vor allem wenn man Übergangsfunktionen vorliest wie: "delta q,a delta q'' , a
Unterscheidet sich die Minimierung eines Transduktors von der eines Akzeptors?
Ich weiß nicht, inwiefern ich die Ausgaben des Transduktors einbeziehen soll.
ja, dazu gibt es auch Arbeiten. Hier zum Beispiel ein Überblicksaufsatz dazu: Choffrut, Christian. "Minimizing subsequential transducers: a survey." Theoretical Computer Science 292.1 (2003): 131-144.
@@andreas.schaefer Was ist wenn im 2. Schritt Das Grüne Feld eines von den ausgegrauten Feldern ist. Wird dann auch ein (*) gemacht oder nur, falls das Grüne Feld ein (*) ist?
Was wäre wenn man zwei Endzustände hätte und diese als Paare in Schritt 1 betrachet, dürften diese ja nicht markiert werden da ja beide qeF. Das "Verschmelzen ist desweiteren auch schlecht bis gar nicht erklärt....und noch weitere Dinge
Zwei Endzustände werden erstmal im ersten Schritt nicht markiert. Das ist auch sinnvoll, falls zum Beispiel beide Endzustände nur Kanten zu sich selbst haben. Dann könnte man die Zustände nämlich zu einem verschmelzen. Falls man jedoch von einem der Endzustände mit z.B. a in einen Endzustand kommt und von dem anderen Endzustand nicht, wird das Paar im zweiten Schritt markiert und die die Zustände sind nicht zu verschmelzen. Verschmelzen bedeutet an dieser Stelle, was man sich intuitiv vorstellen würde. Man malt statt der zu verschmelzenden Zustände nur einen Zustand und alle in einen der Zustände eingehenden oder davon ausgehenden Kanten führen dann zu diesem Zustand. Das funktioniert auch immer, weil die Quell/Zielzustände sofern sie unterschiedlich sind, auch äquivalent sein und verschmolzen werden müssen. Formal bestimmen Sie eine Äquivalenzrelation auf der Zustandsmenge des Ausgangsautomaten und der Minimalautomat hat die Äquivalenzklassen als Zustände.