Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Beide Seiten der vorigen Revision Vorhergehende Überarbeitung Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
faecher:informatik:oberstufe:automaten:dea:start [23.05.2022 18:35] – [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 // | ||
- | |||
- | ===== Definition ===== | ||
- | |||
- | Eine DEA ist ein 5-Tupel '' | ||
- | |||
- | * '' | ||
- | * '' | ||
- | * '' | ||
- | * '' | ||
- | * '' | ||
- | |||
- | Den **Übergang** von einem Zustand zum nächsten bezeichnet man auch als **Transition** oder **Zustandsübergang**. | ||
- | ===== 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/ | ||
- | |||
- | 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: | ||
- | |||
- | ^ δ | ||
- | | 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 im Übergangsdiagramm der Fehlerzustand der Übersichtlichkeit halber weggelassen wurde. 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. | ||
- | </ | ||
- | |||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A1) === | ||
- | |||
- | Gegeben ist der folgende DEA: M = ({z0, | ||
- | |||
- | ^ δ | ||
- | | z0 | z1 | z3 | | ||
- | | z1 | z2 | z0 | | ||
- | | z2 | z3 | z1 | | ||
- | | z3 | z0 | z2 | | ||
- | |||
- | * Welches sind die Zustände des DEA, was der Start, was gültige Endzustände? | ||
- | * Welche Eingaben akzeptiert der Automat? | ||
- | * Erstelle ein Zustandsübergangsdiagramm für den DEA | ||
- | |||
- | ---- | ||
- | {{: | ||
- | === (A2) === | ||
- | |||
- | Entwickle einen DEA, der als Eingabenge | ||
- | |||
- | * Gib einen Übergangsgraphen an | ||
- | * Gib eine Darstellung als Übergangsmatrix an | ||
- | |||
- | == Beispieleingaben: | ||
- | |||
- | 1000111110110 wird akzeptiert | ||
- | 1011101000111 wird nicht akzeptiert | ||
- | |||
- | ++++ Hilfestellung | | ||
- | Betrachte zunächst besondere Wörter wie etwa | ||
- | '' | ||
- | diese akzeptiert werden oder nicht. | ||
- | ++++ | ||
- | {{tag> DEA Übergangsmatrix Übergangsgraph}} |