Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:automaten:dea:start [20.05.2022 16:12] – [Die Übergangsmatrix] sbel
+++ faecher:informatik:oberstufe:automaten:dea:start [Unbekanntes Datum] (aktuell) – gelöscht - Externe Bearbeitung (Unbekanntes Datum) 127.0.0.1
@@ Zeile 1: / Zeile 1: @@
-====== Deterministische endliche Automaten ======
-DEA ist die deutsche Abkürzung für //Deterministischer Endlicher Automat//. Im Englische lautet die Abkürzung DFA für//Deterministic Final Automaton//. Auch in deutschsprachiger Fachliteratur wird oft das Akronym DFA genutzt.
-===== Definition =====
-Eine DEA ist ein 5-Tupel ''DEA = { Q, Σ, δ, E, s}''  er besteht also aus den folgenden 5 Teilen:
-  * ''Q'' Menge aller Zustände (oft auch Z oder S (engl. state))
-  * ''Σ'' Alphabet / Menge der Alphabetzeichen (Sigma)
-  * ''δ'' Übergangsfunktion (Delta)
-  * ''E'' Menge der akzeptierenden Endzustände,
-  * ''s'' Startzustand.
-===== Darstellung =====
-Ein DEA wir häufig durch seinen <color green/lightgrey>Übergangsgraphen</color> dargestellt.Gelegentlich wird auch der Begriff Zustandsübergangsdiagramm verwendet.
-{{ :faecher:informatik:oberstufe:automaten:dea:beispiel.png?500 |}}
-Im Übergangsgraphen sind viele Informationen enthalten:
-  * Q={q0,q1,q2,q3}
-  * Σ={a,b}
-  * δ wird dargestellt durch die Pfeile, die von einem Zustand zum nächsten führen.
-  * E={q3}
-  * s=q0
-==== Die Übergangsmatrix====
-Die Übergangsfunktion δ kann auch als <color green/lightgrey>Übergangsmatrix</color> dargestellt werden. Dabei werden in der ersten Spalte alle Zustände eingetragen und in der ersten Zeile alle Zeichen des Eingabealphabets Σ eingetragen. In den Tabellenzellen wird vermerkt, zu welchem Zustand der Automat wechselt, wenn er zuvor im Zustand der ersten Spalte war und dann die Eingabe der ersten Zeile erfolgt. Die Übergangstabelle für das obige Beispiel sieht also so aus:
-^  δ   ^  a   ^  b   ^
-|  q0  |  q1  |  q2  |
-|  q1  |  q3  |      |
-|  q2  |  q3  |      |
-|  q3  |      |      |
-Das bedeutet im Beispiel: Wenn der Automat sich im Zustand **q1** befindet, und es Erfolgt die Eingabe **a**, wechselt er zum Zustand **q3**. Nun fällt auf, dass die Tabelle unvollständig ist: Wenn der Automat sich im Zustand **q1** befindet, und die Eingabe **b** erfolgt, ist kein Ziel angegeben, denn der Automat akzeptiert an dieser Stelle die Eingabe **b** überhaupt nicht. Das liegt daran, dass das Übergangsdiagramm den Fehlerzustand der Übersichtlichkeit halber weggelassen hat, das vollständige Diagramm sieht so aus:
-{{ :faecher:informatik:oberstufe:automaten:dea:beispiel1.png?500 |}}