Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung Nächste Überarbeitung | Vorherige Überarbeitung | ||
faecher:informatik:oberstufe:automaten:dea:start [24.05.2022 13:13] – [Die Übergangsmatrix] sbel | faecher:informatik:oberstufe:automaten:dea:start [07.12.2023 12:55] (aktuell) – [Die Übergangsmatrix] Svenja Müller | ||
---|---|---|---|
Zeile 14: | Zeile 14: | ||
Den **Übergang** von einem Zustand zum nächsten bezeichnet man auch als **Transition** oder **Zustandsübergang**. | Den **Übergang** von einem Zustand zum nächsten bezeichnet man auch als **Transition** oder **Zustandsübergang**. | ||
+ | |||
+ | <WRAP center round tip 90%> | ||
+ | Ein **deterministischer** Automat (deterministisch = "keine Freiheit", | ||
+ | * Von einem Zustand q1 kann es keine 2 möglichen Übergänge geben, die beide dasselbe Alphabetzeichen verarbeiten. -> Pro Alphabetzeichen gibt es nur einen möglichen Weg! | ||
+ | * Ebenso darf es nur einen einzigen Startzustand geben. | ||
+ | </ | ||
+ | |||
===== Darstellung ===== | ===== Darstellung ===== | ||
- | Ein DEA wir häufig durch seinen <color green/ | + | Ein DEA wir häufig durch seinen <color green/ |
{{ : | {{ : | ||
Zeile 40: | Zeile 47: | ||
| 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 der Fehlerzustand der Übersichtlichkeit halber weggelassen wurde. Das vollständige Diagramm sieht so aus: | 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: | ||
Zeile 64: | Zeile 71: | ||
=== (A1) === | === (A1) === | ||
- | Gegeben ist der folgende DEA: M = ({z0, | + | Gegeben ist der folgende DEA: M = ({z0, |
^ δ | ^ δ | ||
Zeile 80: | Zeile 87: | ||
=== (A2) === | === (A2) === | ||
- | Entwickle einen DEA, der als Eingabmenge | + | Entwickle einen DEA, der als Eingabemenge |
* Gib einen Übergangsgraphen an | * Gib einen Übergangsgraphen an | ||
Zeile 112: | Zeile 119: | ||
aaaaaa | 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 ==== | ==== Material ==== |