faecher:informatik:oberstufe:automaten:dea:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:automaten:dea:start [23.05.2022 16:26] – [Die Übergangsmatri x] sbelfaecher:informatik:oberstufe:automaten:dea:start [11.03.2025 14:24] (aktuell) – Marco Kuemmel
Zeile 1: Zeile 1:
 ====== Deterministische endliche Automaten ====== ====== 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 ===== ===== Definition =====
  
-Eine DEA ist ein 5-Tupel ''DEA = { Q, Σ, δ, E, s}''  er besteht also aus den folgenden 5 Teilen:+Ein DEA ist ein 5-Tupel ''DEA = { Q, Σ, δ, E, s}''  er besteht also aus den folgenden 5 Teilen:
  
   * ''Q'' Menge aller Zustände (oft auch Z oder S (engl. state))   * ''Q'' Menge aller Zustände (oft auch Z oder S (engl. state))
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** 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 ===== ===== 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 |}} {{ :faecher:informatik:oberstufe:automaten:dea:beispiel.png?500 |}}
Zeile 30: Zeile 39:
 ==== Die Übergangsmatrix==== ==== Die Übergangsmatrix====
  
-Die Übergangsfunktion δ kann auch als <color green/lightgrey>Übergangsmatrix</color> oder <color green/lightgrey>Übergangstabelle</color>dargestellt werden. Dabei werden in der ersten Spalte alle Zustände eingetragen und in der ersten Zeile alle Zeichen des Eingabealphabets Σ eingetragen. +Die Übergangsfunktion δ kann auch als <color green/lightgrey>Übergangsmatrix</color> oder <color green/lightgrey>Übergangstabelle</color> dargestellt werden. Dabei werden in der ersten Spalte alle Zustände eingetragen und in der ersten Zeile alle Zeichen des Eingabealphabets Σ eingetragen. 
  
 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: 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 40: Zeile 49:
 |  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**. +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: 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) === === (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?    * 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   * Erstelle ein Zustandsübergangsdiagramm für den DEA
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A2) ===
 +
 +Entwickle einen DEA, der als Eingabemenge  Σ={0,1} hat, und alle Eingaben akzeptiert, die auf  ''10'' enden.
 +
 +  * 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
 +''0'' oder '''' (leeres Wort) und entscheide, ob
 +diese akzeptiert werden oder nicht.
 +++++
 +
 +----
 +{{:aufgabe.png?nolink  |}}
 +=== (A3) ===
 +
 +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 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 ====
 +
 +{{simplefilelist>.:*}}
 +
 +{{tag> DEA Übergangsmatrix Übergangsgraph}}
  • faecher/informatik/oberstufe/automaten/dea/start.1653323213.txt.gz
  • Zuletzt geändert: 23.05.2022 16:26
  • von sbel