Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:dea:start [20.05.2022 15:15] – angelegt sbel
+++ faecher:informatik:oberstufe:automaten:dea:start [20.05.2022 16:00] – [Die Übergangsmatrix] sbel
@@ 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.
+^  δ   ^  a   ^  b   ^
+|  q0  |  q1  |  q2  |
+|  q1  |  q3  |      |
+|  q2  |  q3  |      |
+|  q3  |      |      |