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 14:12] – [Die Übergangsmatrix] sbel | faecher:informatik:oberstufe:automaten:dea:start [30.01.2023 15:50] – Marco Kuemmel | ||
---|---|---|---|
Zeile 5: | Zeile 5: | ||
===== Definition ===== | ===== Definition ===== | ||
- | Eine DEA ist ein 5-Tupel '' | + | Ein DEA ist ein 5-Tupel '' |
* '' | * '' | ||
Zeile 12: | Zeile 12: | ||
* '' | * '' | ||
* '' | * '' | ||
+ | |||
+ | Den **Übergang** von einem Zustand zum nächsten bezeichnet man auch als **Transition** oder **Zustandsübergang**. | ||
+ | |||
+ | <WRAP center round important 90%> | ||
+ | Eine entscheidende Eigenschaft des DEA ist, dass jeder Zustandsübergang eindeutig sein muss (daher das Wort deterministisch)! Von einem Zustand q1 kann es also z. B. keine 2 möglichen Übergänge geben, die beide dasselbe Alphabetzeichen ' | ||
+ | </ | ||
===== Darstellung ===== | ===== Darstellung ===== | ||
Zeile 29: | Zeile 35: | ||
==== Die Übergangsmatrix==== | ==== Die Übergangsmatrix==== | ||
- | Die Übergangsfunktion δ kann auch als <color green/ | + | 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: | ||
^ δ | ^ δ | ||
Zeile 37: | Zeile 45: | ||
| q3 | | | | | q3 | | | | ||
- | Das bedeutet im Beispiel: Wenn der Automat sich im Zustand **q1** befindet, und es Erfolgt | + | Das bedeutet im Beispiel: Wenn der Automat sich im Zustand **q1** befindet, und es erfolgt |
+ | |||
+ | 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 | ||
{{ : | {{ : | ||
+ | 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? FIXME | ||
+ | * Erstelle ein Zustandsübergangsdiagramm für den DEA | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A2) === | ||
+ | |||
+ | Entwickle einen DEA, der als Eingabmenge | ||
+ | |||
+ | * 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. | ||
+ | ++++ | ||
+ | |||
+ | ---- | ||
+ | {{: | ||
+ | === (A3) === | ||
+ | |||
+ | Es soll ein Automat entworfen werden, der alle Worte der Form a< | ||
+ | |||
+ | * Gib einen Übergangsgraphen an | ||
+ | * Gib eine Darstellung als Übergangsmatrix an | ||
+ | |||
+ | == Beispieleingaben: | ||
+ | |||
+ | aaa wird akzeptiert | ||
+ | aaaa wird akzeptiert | ||
+ | aaaaa wird nicht akzeptiert | ||
+ | aaaaaa | ||
+ | |||
+ | |||
+ | ++++ Hilfestellung 1 | Welche Eingaben akzeptiert der folgende Automat? | ||
+ | |||
+ | {{ : | ||
+ | |||
+ | Wie würde ein Automat aussehen, der allen Eingaben akzeptiert, bei denen die Anzahl der a's durch 4 teilbar ist? | ||
+ | |||
+ | |||
+ | |||
+ | ++++ | ||
+ | |||
+ | ++++ Hilfestellung 2 - Antwort auf die Frage aus Hilfestellung 1 | | ||
+ | {{ : | ||
+ | ++++ | ||
+ | |||
+ | |||
+ | ++++ Hilfestellung 3 | Welches ist die erste Anzahl von a's, bei denen beide Kriterien zutreffen? Welche Zustände zuvor sind gültige Endzustände? | ||
+ | |||
+ | ++++ | ||
+ | |||
+ | ++++ Lösung | | ||
+ | {{ : | ||
+ | ++++ | ||
+ | |||
+ | ==== Material ==== | ||
+ | |||
+ | {{simplefilelist> | ||
+ | |||
+ | {{tag> DEA Übergangsmatrix Übergangsgraph}} |