Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- faecher:informatik:oberstufe:automaten:mealy:start [31.05.2022 08:34] – angelegt sbel
+++ faecher:informatik:oberstufe:automaten:mealy:start [21.06.2022 14:23] – [Grundlagen und Übergangsgraph] sbel
@@ Zeile 1: / Zeile 1: @@
+{{ :faecher:informatik:oberstufe:automaten:mealy:mealy.png?180|}}
 ====== Mealy-Automaten ======
+((Diese Wiki-Seite basiert auf Material der ZPG INformatik/BW und steht unter einer [[https://creativecommons.org/licenses/by-nc-sa/3.0/de/|CC-BY-NC-SA Lizenz]]. Als Autoren sind angegeben "Dietrich, Lautebach (2020)".))
+===== Grundlagen und Übergangsgraph =====
@@ Zeile 8: / Zeile 15: @@
   * ... die Tasten A, C und S hat (für Apfelsaft, Cola und Stop)
   * ... 1EUR- und 2EUR-Münzen annimmt.
+Damit ist sein **Eingabealphabet Σ** = {c, a, s, 1, 2}. Anders als ein DEA bewirkt bei einem Mealy-Automaten jede Eingabe eine Ausgabe, das **Ausgabealphabet Δ** = {"Guthaben 1€", "Guthaben 2€", "1€" , "2€", "Apfelsaftflasche", "Colaflasche"}
+<WRAP center round tip 90%>
+Eine Mealy-Maschine oder ein **Mealy-Automat** ist durch ein 6-Tupel ''M = (Q,Σ,∆,δ,λ,q₀)'' definiert.
+Die verwendeten Symbole haben folgende Bedeutungen:
+  * Q: endliche Menge der Zustände<br>
+  * Σ: Eingabealphabet<br>
+  * ∆: Ausgabealphabet<br>
+  * δ: totale Überführungsfunktion Q x Σ → Q
+  * λ: totale Ausgabefunktion Q x Σ → ∆
+  * q0: Anfangszustand, q0 ∈ Q
+Die Maschine erzeugt in jedem Übergang eine Ausgabe.
+</WRAP>
+Die Überführungsfunktion δ und die Ausgabefunktion λ können wie beim DEA auch, in einem **Übergangsgraphen** dargestellt werden. Ein passender **Übergangs-** oder **Transitionsgraph** sieht folgendermaßen aus:
+{{ :faecher:informatik:oberstufe:automaten:mealy:mealy-transistion.png?600 |}}
+Anders als beim DEA muss zu jedem Übergang außer der Eingabe auch die Ausgabe notiert werden, dies geschieht für gewöhnlich durch ein Trennzeichen wie '';'' oder ''/''.
+Der Automat befindet sich immer in genau einem der Zustände  und beginnt dabei immer im so genannten **Startzustand**, der mit einem zusätzlichen Pfeil gekennzeichnet wird (hier q0).
+Jede Eingabe bewirkt einen Übergang (auch Transition genannt) zu einem anderen Zustand, dargestellt durch einen Pfeil.
+<WRAP center round info 90%>
+Bei Mealy-Automaten gehört zu einem Übergang auch eine Ausgabe.
+</WRAP>
+Vom Startzustand ''q0'' aus wird durch Einwurf von ''1€'' der Zustand ''q2'' erreicht und die Ausgabe ''Guthaben: 1,00'' erzeugt.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A1) ===
+Baue den Getränkeautomaten in [[https://flaci.com/autoedit|FLACI]] auf und teste ihn in der Simulation.
+  * Erzeuge einen neuen Mealy-Automaten
+  * Schalte im Reiter ''Definition'' die Option für ''δ und λ als partielle Funktionen'' an
+  * Definiere im Reiter ''Alphabet'' das Eigabe- und das Ausgabealphabet
+  * Überführe den Übergangsgraphen von oben nach FLACI
+  * Simuliere Eingaben
+Welche Funktion hat die Option ''δ und λ als partielle Funktionen'', was verändert sich wenn man diese Option deaktiviert.
+----
+===== Übergangstabelle =====
+Und wie bei [[..:dea:start|DEAs]] kann man die Übergangsfunktion ''δ'' und die Ausgabefunktion ''λ'' auch hier als **Übergangsmatrix/Übergangstabelle** darstellen, anstelle des Übergangsgraphen. Wie bei den DEAs gilt: Im Graph kann man den Fehlerzustand der Übersichtlichkeit wegen weglassen, in der Übergangsmatrix wird dieser stets angegeben.
+|                   | Eingaben → (Folgezustand / Ausgabe)                       |||||
+^  Ausgangszustand  ^  1€                                  ^  2€  ^  c  ^  a  ^  s  ^
+|  q0               |  q2/"Guthaben 1€"                              |      |     |     |     |
+|  q1               |                                      |      |     |     |     |
+|  q2               |                                      |      |     |     |     |
+|  qF               |                                      |      |   qF  |     |     |
+----
+{{:aufgabe.png?nolink  |}}
+=== (A2) ===
+Vervollständige anhand des Übergangsgraphen die Übergangsmatrix
+----
+{{:aufgabe.png?nolink  |}}
+=== (A3) ===
+Schalte  die Option ''δ und λ als partielle Funktionen'' in FLACI aus und ergänze den Automaten in FLACI um den Fehlerzustand. Überprüfe so deine Tabelle aus der vorigen Aufgabe.
+===== Übungen =====
+{{:aufgabe.png?nolink  |}}
+=== (A4) ===
+Gib eine Eingabe an, die zur Ausgabe ''Apfelsaftflasche'' führt.
+----
+{{:aufgabe.png?nolink  |}}
+=== (A5) ===
+Gib die Ausgabe an, die zur Eingabe ''1€,s'' gehört. In welchem Zustand befindet sich der Automat anschließend?
+----
+{{:aufgabe.png?nolink  |}}
+=== (A6) ===
+Modelliere einen Mealy-Automaten für einen Automaten aus der Schule. Gib die folgenden Informationen an:
+  * Eingabealphabet, Zustandsmenge, Startzustände und Ausgabealphabet
+  * Zustandsübergangs- und Ausgabefunktionen als Tabelle
+  * Zustandsübergangsgraph
+----
+{{:aufgabe.png?nolink  |}}
+=== (A7) ===
+Ein Mealy-Automat A ist durch den folgenden Übergangsgraphen gegeben:
+{{ :faecher:informatik:oberstufe:automaten:mealy:mealy-aufgabe.png |}}
+  * Gib die Ausgabe zur Eingabe ''uhuhuhuuhhuhu'' an
+  * Beschreibe A als 6-Tupel. Lege die Übergangsfunktion δ sowie die Ausgabefunktion γ durch eine Tabelle fest.
+  * Beschreibe die "Übersetzungsfunktion" - wann gibt der Automat einen 1 aus?