Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

--- faecher:informatik:oberstufe:automaten:dea:start [23.05.2022 19:30] – [Die Übergangsmatrix] sbel
+++ faecher:informatik:oberstufe:automaten:dea:start [11.03.2025 14:24] (aktuell) – Marco Kuemmel
@@ 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.
+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 =====
@@ Zeile 14: / Zeile 14: @@
 Den **Übergang** von einem Zustand zum nächsten bezeichnet man auch als **Transition** oder **Zustandsübergang**.
+<WRAP center round tip 90%>
+Ein **deterministischer** endlicher Automat (deterministisch = klar definierte Zustände & Übergänge, daher reproduzierbare Verarbeitung) hat bestimmte Eigenschaften:
+  * 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.
+Das Wort **endlich** bezieht sich darauf, dass es eine endliche Menge von Zuständen gibt (also nicht //unendlich// viele).
+</WRAP>
 ===== Darstellung =====
-Ein DEA wir häufig durch seinen <color green/lightgrey>Übergangsgraphen</color> dargestellt.Gelegentlich wird auch der Begriff Zustandsübergangsdiagramm verwendet.
+Ein DEA wird häufig durch seinen <color green/lightgrey>Übergangsgraphen</color> dargestellt. Gelegentlich wird auch der Begriff <color green/lightgrey>Zustandsübergangs**diagramm**</color> verwendet.
 {{ :faecher:informatik:oberstufe:automaten:dea:beispiel.png?500 |}}
@@ Zeile 40: / Zeile 49: @@
 |  q3  |      |      |
-Das bedeutet im Beispiel: Wenn der Automat sich im Zustand **q1** befindet, und es Erfolgt die Eingabe **a**, wechselt er zum Zustand **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:
@@ Zeile 64: / Zeile 73: @@
 === (A1) ===
-Gegeben ist der folgende DEA: M = ({z0,z1,z2,z3}, {apfel,birne}, δ, z0, {z3}). δ ist in Form einer Übergangstabelle gegeben:
+Gegeben ist der folgende DEA: M = ({z0,z1,z2,z3}, {apfel,birne}, δ, {z0}, z3). δ ist in Form einer Übergangstabelle gegeben:
-^  δ   ^  a   ^  b   ^
+^  δ   ^  apfel  ^  birne  ^
-|  z0  |  z1  |  z3  |
+|  z0  |  z1     |  z3     |
-|  z1  |  z2  |  z0  |
+|  z1  |  z2     |  z0     |
-|  z2  |  z3  |  z1  |
+|  z2  |  z3     |  z1     |
-|  z3  |  z0  |  z2  |
+|  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
@@ Zeile 80: / Zeile 88: @@
 === (A2) ===
-Entwickle einen DEA, der als Eingabenge  Σ={0,1} hat, und alle Eingaben akzeptiert, die auf  ''10'' enden.
+Entwickle einen DEA, der als Eingabemenge  Σ={0,1} hat, und alle Eingaben akzeptiert, die auf  ''10'' enden.
   * Gib einen Übergangsgraphen an
@@ Zeile 100: / Zeile 108: @@
 === (A3) ===
-Es soll ein Automat entworfen werden, der alle Worte der Form a<sup>n</sup> (also a, aa, aaa, aaaa, u.s.w.) besteht, wobei n durch 3 oder durch 4 (oder durch beide) teilbar ist.
+Es soll ein DEA entworfen werden, der alle Worte der Form a<sup>n</sup> (also a, aa, aaa, aaaa, u.s.w.) versteht, wobei n durch 3 oder durch 4 (oder durch beide) teilbar ist.
+  * Gib einen Übergangsgraphen an
+  * Gib eine Darstellung als Übergangsmatrix an
 == Beispieleingaben: ==
   aaa      wird akzeptiert
-  aaaa     wird akzeptier
+  aaaa     wird akzeptiert
   aaaaa    wird nicht akzeptiert
   aaaaaa   wird akzeptiert
+++++ Hilfestellung 1 | Welche Eingaben akzeptiert der folgende Automat?
+{{ :faecher:informatik:oberstufe:automaten:dea:as0.png?400 |}}
+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 |
+{{ :faecher:informatik:oberstufe:automaten:dea:as01.png?400 |}}
+++++
+++++ Hilfestellung 3 | Welches ist die erste Anzahl von a's, bei denen beide Kriterien zutreffen? Welche Zustände zuvor sind gültige Endzustände? Was passiert bei längeren Eingabeworten?
+++++
+++++ Lösung |
+{{ :faecher:informatik:oberstufe:automaten:dea:as2.png?400 |}}
+++++
 ==== Material ====