Automaten

1. Zustandsgraph / Zustandsdiagramm:
    
   • jeder Zustand wird mit einem Kreis dargestellt (Knoten im Diagramm)
   • von jedem Zustand führen Pfeile (Kanten) zu allen möglichen Folgezuständen
   • es gibt einen Anfangszustand, der mit einem kleinen Pfeil gekennzeichnet wird
   • Endzustände erhalten einen doppelten Kreis
   • die Pfeile (Kanten) werden mit den Eingabezeichen beschriftet, die den Übergang auslösen (bei mehreren Möglichkeiten Verknüpfung mit "v")
   • Ausgabezeichen werden ebenfalls an die entsprechenden Kanten neben die Eingabezeichen geschrieben.
   
   

   Vereinbarung:

   Die Zustände werden von 0 ab durchnummeriert, 0 ist der Anfangszustand. Bei nur einem Endzustand hat dieser die höchste Zustandsnummer.

   
    
2. Zustandstabellen:
    

   horizontal:		alle möglichen Eingabezeichen
   vertikal:		alle möglichen (Ausgangs-)Zustände
   Kreuzungspunkte:		Folgezustand und Ausgabezeichen
   Endzustände:		kein Eintrag

   
    
3. Endliche Automaten:
    
   Def: Ein endlicher Automat ist festgelegt durch
   • eine endliche Menge von Zuständen (Zustandsmenge)
   • eine endliche Menge von Eingabezeichen (Eingabemenge)
   • eine endliche Menge von Ausgabezeichen (Ausgabemenge)
   • ein Automatenprogramm, das jeder Kombination von Zustand und Eingabezeichen eine Kombination von Ausgabezeichen und Folgezustand zuordnet