Zur Themenübersicht     

Definition: Erkennender Automat


Definition eines erkennendenchen Automaten (EA)

(auch Akzeptor genannt):

  1. Ein EA besitzt ein endliches Eingabealphabet E = {ei; e2; … en} ,
  2. eine endliche Zustandsmenge Z = {zi; z2; … zn},
  3. einen definierten Anfangszustand z0 Î Z
  4. und eine Teilmenge Za Í Z der Zustandsmenge, genannt akzeptierende Zustände. 
  5. Die Übergänge von einem Zustand zu einem anderen Zustand werden durch eine  Übergangsfunktion f beschrieben: 

    f: ( zi Î Z ; ej Î E ) à z k Î Z


    Sie ordnet jedem Zustand und jeder möglichen Eingabe genau einen Folgezustand zu.
  6. Ein Eingabewort ist eine Folge von Zeichen aus dem Eingabealphabet. Um zu prüfen, ob ein Eingabewort akzeptiert wird,  wird das Wort Zeichen für Zeichen gelesen und dem Automaten übergeben. Dieser durchläuft dann entsprechend der Übergangsfunktion verschiedene Zustände. Der Automat akzeptiert das Eingabewort genau dann, wenn er sich nach dem Bearbeiten des letzten Zeichens des Eingabewortes in einem akzeptierendem Zustand befindet.