Endliche, erkennende und Kellerautomaten

können lediglich eine bestimmte, eine endliche, Anzahl Zustände abbilden

Eingabealphabet und Ausgabealphabet haben endlich viele Zeichen

es wird unterschieden in:

• endliche Automaten ohne Ausgabe

• endliche Automaten mit Ausgabe

weitere Unterscheidung in:

• deterministischen endlichen Automaten

• nichtdeterministischen endlichen Automaten

endlicher Automat ohne Ausgabe

ändert nur seine Zustände

Beispiele:

• Aufzug

• Lichtschalter

• Ampel

endlicher Automat mit Ausgabe

können auch mehrere Ausgaben sein

Beispiel: Fahrkartenautomat

Ausgabe muss nicht mit Endzustand übereinstimmen

es wird unterschieden in:

• Moore-Automat

• Mealy-Automat

liefert für einen bestimmten Zustand eine bestimmte Ausgabe

Beispiel: in Fahrscheinautomat befinden sich zwei Moore-Automaten. Der erste gibt den den Fahrschein aus, wenn der Fahrpreis vollständig bezahlt ist. Der zweite gibt das überzählige Restgeld aus.

Zustand -> Ausgabe

die Ausgabe hängt sowohl von der Eingabe als auch vom Zustand ab

Beispiel: Anzeige eines noch zu zahlenden Betrags bei einem Fahrscheinautomaten

DEA

wenn das Verhalten vorhersagbar ist, wenn also ein Wechsel von genau einem Zustand zu genau einem anderen Zustand führt

Beispiel:

• Lichtschalter

• Fahrstuhl

• Fahrkartenautomat

NEA

wenn Verhalten nicht vorhersagbar ist, wenn also nicht eindeutig klar ist, zu welchem anderen Zustand ein Übergang führt

Beispiel:

• Schalter, der nach dem Zufallsprinzip das Licht entweder an oder ausschaltet

auch Akzeptor genannt

er stellt sicher, dass die Eingabe zum Eingabealphabet gehört, dass sie korrekt ist

wechselt nur dann seinen Zustand, wenn er ein Zeichen der Eingabe akzeptiert -> erreicht nur dann Endzustand, wenn er alle Zeichen der Eingabe akzeptiert -> Sichergestellt, dass die EIngabe korrekt ist

erzeugt keine Ausgabe

liefert allein durch das Erreichen des Endzustands, dass Eingabe komplett verarbeitet und korrekt ist

auch Stackmaschine gennant

hat die Möglichkeit Eingaben zu speichern

verfügt zusätzlich über einen Speicher

Ablage erfolgt strikt von oben nach unten, Lesen nach LIFO

Beim Lesen werden die Daten aus dem Speicher genommen