faecher:informatik:oberstufe:automaten:mealy:start []

Diese Seite ist nicht editierbar. Du kannst den Quelltext sehen, jedoch nicht verändern. Kontaktiere den Administrator, wenn du glaubst, dass hier ein Fehler vorliegt.
{{ :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 =====


Die sogenannten **Mealy-Automaten** können in jedem Schritt außer der Änderung des internen Zustands auch eine **Ausgabe** erzeugen und erlauben damit die Modellierung z.B. von Getränke-, Fahrkarten- oder ähnlichen Automaten, die wir aus unserer Umwelt kennen.

Als Beispiel soll ein Getränkeautomat dienen, der...

  * ... die Tasten A, C und S hat (für Apfelsaft, Cola und Stop) 
  * ... 1€- und 2€-Münzen annimmt.

Damit ist sein **Eingabealphabet Σ** = {a, c, s, 1, 2}. Anders als ein DEA bewirkt bei einem Mealy-Automaten jede Eingabe eine Ausgabe aus dem **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
  * Σ: Eingabealphabet
  * ∆: Ausgabealphabet
  * δ: Übergangsfunktion Q x Σ → Q
  * λ: 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:getraenkeautomat.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 ''q1'' erreicht und die Ausgabe ''Guthaben: 1,00'' erzeugt.

----
Nachfolgende Aufgaben können teilweise sowohl mit der Webseite [[https://flaci.com/autoedit|FLACI]], also auch mit dem Java-Tool [[https://www.jflap.org/jflaptmp/|JFLAP]] bearbeitet werden!

{{:aufgabe.png?nolink  |}}
=== (A1) ===

++++ Bearbeitung mit FLACI|
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 Eingabe- 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.
++++

++++ Bearbeitung mit JFLAP|
Baue den Getränkeautomaten in [[https://www.jflap.org/jflaptmp/|JFLAP]] auf und teste verschiedene Eingaben.

  * Wähle den Mealy-Automaten
  * Erstelle den Automaten und trage in allen Übergängen sowohl die Eingabe, als auch die Ausgabe in das jeweilige Feld ein.
  * Erstelle verschiedene Eingaben z. B. mit Input -> Step. **Wichtig:** Jeder Input muss die __komplette__ Eingabe enthalten (z. B.: "1€1€C")
  * Klicke links unten auf "Step", um die Eingabe zu testen.
++++
----

===== Ü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               |  q1/"Guthaben 1€"                    |      |      |     |     |
|  q1               |                                      |      |      |     |     |
|  q2               |                                      |      |      |     |     |
|  qF               |                                      |      |  qF  |     |     |


----
{{:aufgabe.png?nolink  |}}
=== (A2) ===

Vervollständige anhand des Übergangsgraphen die Übergangsmatrix


----
{{:aufgabe.png?nolink  |}}
=== (A3) ===
Falls du mit FLACI arbeitest:\\
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 eine 1 aus?