Akzeptor und Sprache

Endliche Automaten ohne Ausgabe - Akzeptor

Ein Safe öffnet sich nur dann, wenn die vierstellige Ziffernkombination korrekt eingegeben wurde. Ein Smartphone lässt sich nur dann bedienen, wenn eine PIN oder der Fingerabdruck korrekt sind. Beide Fälle lassen sich durch einen Automaten beschreiben. Eine Ausgabe nach jedem Schritt ist jedoch nicht mehr erforderlich. Erst am Ende der Eingabe muss entschieden werden, ob diese akzeptiert oder nicht akzeptiert wird. Solche Automaten nennt man Akzeptoren.

Definition des Akzeptors - Automat ohne Ausgabe

Ein Akzeptor A = (X, Z, δ, z₀, Z_E) ist ein endlicher Automat ohne Ausgabe. Dabei gilt:

• • X ... Eingabealphabet (nichtleere, endliche Menge)
  • Z ... Zustandsmenge (nichtleere, endliche Menge)
  • δ ... Überführungsfunktion, welche jedem Paar (Eingabezeichen, Zustand) genau einen Folgezustand zuordnet
  • z₀ ∈ Z ist der Anfangszustand
  • Z_E ... Endzustandsmenge (endliche Teilmenge von Z)

Aufbau eines Funktionsmodells

Arbeitsweise

• SOLANGE sich in der Zelle des Lesekopfs ein Zeichen befindet:
  • Lies mithilfe des Lesekopfs das Zeichen aus der aktuellen Zelle des Eingabebands
  • Wechsle in Abhängigkeit vom aktuellen Zustand und dem gelesenen Zeichen in einen Folgezustand.
  • Bewege das Band eine Zelle weiter.
• Nachdem das gesamte Eingabewort gelesen wurde, wird geprüft, ob sich der Automat in einem Endzustand befindet. Ist dies der Fall, wird das Wort akzeptiert.

Wörter und Sprache

• Ein Wort w ist eine endliche Folge von Zeichen aus einem Alphabet X.
• Die Menge aller Wörter w über einem Alphabet X wird mit X* bezeichnet  und ist ist unendlich groß. Sie enthält auch das leere Wort. Das Zeichen ε bezeichnet das leere Wort, das aus keinem Zeichen besteht.
  Beispiel: Wenn X = {a, b}, dann ist die Menge aller Wörter X* = {ε, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, bbb, aaaa, aaab, ...}.
  Da Wörter beliebig lang sein können, enthält X* bei einem nichtleeren Alphabet unendlich viele Wörter.
• Die Sprache eines Automaten L(A) ist die Menge aller Wörter über dem Alphabet X, die A nach vollständiger Abarbeitung von w in einen Endzustand überführen. 
• Die Sprache kann verbal, durch die Angabe eines Musters, mathematisch oder durch Auflisten aller Wörter beschrieben werden, beispielsweise so:
  L(A) = {00, 000, 100, 0000, 0100, 1000, 1100, …} 
  L(A) ist die Menge aller Binärzahlen, deren letzte beiden Bits Null sind. 
  L(A) = {w | w ∈ X* und w endet auf 00}
  Interpretiert man diese Wörter als Binärzahlen, stellen sie Zahlen dar, die durch 4 teilbar sind.

Beispiel: Safe mit vierstelligem Ziffernschloss

Ein elektronischer Safe lässt sich nur dann öffnen, wenn die Ziffernkombination 0815 eingegeben wird. Alle anderen Eingaben sperren den Safe dauerhaft.

Dies lässt sich als Akzeptor A = (X, Z, δ, q₀, Z_E) modellieren mit

• • X = {0, 1, ..., 9}
  • Z = {q₀, q₁, q₂, q₃, q_4, q₅}
  • δ als Tabelle
    
    oder als Graph
    
  • q₀
  • Z_E = {q₄}

Die Sprache L(A) des Automaten besteht einzig aus dem Wort w = 0815, L(A) = {0815}.