Buch druckenBuch drucken

Kaffee-Automat "Pott-1"

Website: Informatik_moodle
Kurs: Automaten
Buch: Kaffee-Automat "Pott-1"
Gedruckt von: Gast
Datum: Freitag, 3. Mai 2024, 11:14

Beschreibung

Ausgehend von einem realen Automaten wollen wir einen kurzen Einblick in das Thema endliche Automaten der theoretischen Informatik geben.

Inhaltsverzeichnis

Reale Automaten

banditautomatAutomaten findet man heute überall. Geldautomaten, Getränkeautomaten, Spielautomaten, Fahrstühle, Lichtschalter, ...

Was haben diese "Geräte" gemeinsam?

  • Sie warten auf Eingaben
  • Sie haben ein Gedächtnis
  • Sie produzieren meist Ausgaben

Was kann Pott-1?

pottUnser Kaffee-Automat verkauft nur einen Artikel: "1 Pott Kaffee, schwarz, ungesüßt für 1,50 €"
Der Automat akzeptiert nur 1€- und 50Cent-Münzen. Andere Münzen und Eingaben werden einbehalten und als "Falschgeld" behandelt.
Sobald der Betrag von 1,50€ (mit gültigen Münzen) erreicht wird, kann der Kaffee in Strömen fließen. Vorher sollte der Pott druntergestellt werden.

Was sind das für Zustände?

Wir untersuchen nun die Frage:
Welche Eingabe veranlasst den Automaten zu welcher Ausgabe? Nach kurzer Überlegung wird klar, dass wir auch den momentanen Zustand des Automaten berücksichtigen müssen!
Ist Pott-1 im Zustand "Ich habe 100 Cent", so führt die Eingabe von 50 Cent zur Ausgabe von KAFFEE.

Befindet sich Pott-1 hingegen im Zustand "Ich habe 50 Cent", so führt die gleiche Eingabe zur Ausgabe von NICHTS.

Automatenmodell Pott-1

Pott-1 ist ein endlicher Automat: EA
die Menge der Eingaben, Ausgaben und Zustände ist jeweisl endlich

Pott-1 ist ein deterministischer, endlicher Automat: DEA
er wechselt nach einer gültigen Eingabe von einem Zustand, in dem er sich gerade befindet, immer in einen eindeutig bestimmten Folgezustand

Was wissen wir alles über Pott-1:

Eingabe: 1-Euro-Münze oder 50-Cent-Münze
Eingabealphabet= E{1 | 50}
Ausgabe: Kaffee oder kein Kaffee
Ausgabealphabet: A={Kaffee | nichts}
Innere Zustände:
z0 (kein Geld) z1 (50 Cent) z2 (1 €)

Nun müssen noch Übergangsfunktionen beschrieben werden, die unter Beachtung des momentanen Zustands und der Eingabe => den Folgezustand und die mögliche Ausgabe realisieren.

Zustandsgraf für Automaten

Die grafische Darstellung der Übergangsfunktionen nennt man Zustandsgraf, Zustandsdiagramm oder Transpositionsgraf

Diese beschreibende Sprache hat folgende Elemente:

zustandsdiagramm

Zustandsgraf für Pott-1

pott-1-zustandsgraf

Vorgehen:

  • zeichne, platziere zunächst alle Zustände
  • führe von jedem Zustand für jede mögliche Eingabe einen Pfeil zum Folgezustand






Was stimmt hier nicht?

Was stimmt an diesem Grafen nicht?
pott-zg

  • Falschgeld befand sich nicht in unserem Eingabealphabet
    • ergänze das Eingabealphabet!
  • der Übergang von z2 zu z0 muss lauten 1 oder 0,5 / Kaffee
    • oder zeichne einen separaten Pfeil für die Eingabe 1

Automatentabelle

Zustände und Eingaben sowie Übergänge zu Folgezuständen und Ausgaben werden in der Automatentafel übersichtlich dargestellt.

tabelle-Pott-1