Akzeptor

Aus Informatik
Wechseln zu: Navigation, Suche
Definition: Akzeptor

Ein erkennender, endlicher Automat (Akzeptor) ist ein 5-Tupel A:= ( Z, X, \delta ,z_o, Z_E) , wobei gilt:

  • X ist eine nichtleere, endliche Menge, das Eingabealphabet, wobei gilt:  x \in X
  • Z ist eine nichtleere, endliche Menge, die Zustandsmenge, wobei gilt:  z \in Z
  • \delta ist die Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) einen Folgezustand zuordnet:  \delta : X \times Z \to z
  • z_0 \in Z ist der Anfangszustand
  • Z_E \subseteq Z ist eine Teilmenge von Z, die Endzustandsmenge

Funktionsweise und Erklärung

Die Unterschiede zwischen Akzeptor und Transduktor liegen darin, dass ein Akzeptor keine Ausgaben besitzt, aber dafür ein oder mehrere Endzustände. Ein Akzeptor akzeptiert und erkennt ein Eingabewort und signalisiert durch seinen Endzustand das Ergebnis nach außen.

Darüber hinaus sind Endzustände nicht als eine Kombination von Sackgasse und Einbahnstraße zu verstehen. Ist der Automat nach dem kompletten Einlesen des Eingabewortes in einem Endzustand, so akzeptiert er. Ist er nicht in einem Endzustand bei Ende des Wortes, so verwirft er es. Sollte ein Wort noch nicht zu Ende sein und ein Automat erreicht einen Endzustand, wird dieser als "normaler" Zustand behandelt.

Beispiel

Hier ein einfaches Beispiel für einen Akzeptor. Welche Eingabeworte werden akzeptiert?

 BeispielAkzeptor00.png