Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
faecher:informatik:oberstufe:automaten:dea:start [20.05.2022 15:33] – sbel | faecher:informatik:oberstufe:automaten:dea:start [20.05.2022 16:16] – [Die Übergangsmatrix] sbel | ||
---|---|---|---|
Zeile 9: | Zeile 9: | ||
* '' | * '' | ||
* '' | * '' | ||
- | * '' | + | * '' |
* '' | * '' | ||
* '' | * '' | ||
+ | |||
+ | ===== Darstellung ===== | ||
+ | |||
+ | Ein DEA wir häufig durch seinen <color green/ | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Im Übergangsgraphen sind viele Informationen enthalten: | ||
+ | |||
+ | * Q={q0, | ||
+ | * Σ={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/ | ||
+ | |||
+ | ^ δ | ||
+ | | 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: | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Die vollständige Übergangsmatrix sieht also so aus: | ||
+ | |||
+ | ^ δ | ||
+ | | q0 | q1 | q2 | | ||
+ | | q1 | q3 | qF | | ||
+ | | q2 | q3 | qF | | ||
+ | | q3 | qF | qF | | ||
+ | | qF | qF | qF | | ||
+ | |||
+ | <WRAP center round important 90%> | ||
+ | Während man in Zustandsübergangsdiagrammen den Fehlerzustand meist weglässt, um die Übersichtlichkeit zu verbessern, wird der Fehlerzustand bei der Darstellung von δ als Übergangsmatrix für gewöhnlich angegeben. | ||
+ | </ | ||
+ |