In den Abiturvorgaben gehören endliche Automaten und formale Sprachen zum Bereich III.

• Modellieren kontextbezogener Problemstellungen als deterministische endliche Automaten
• Darstellung von deterministischen endlichen Automaten als Graph und als Tabelle
• Formale Sprachen: Reguläre Sprachen und ihre Grammatiken

Dabei bedeutet deterministisch, das die Ausgabe des Automaten in Abhängigkeit von Eingabe und Zustand eindeutig ist, und endlich, dass die Menge der Eingaben und Ausgaben begrenzt ist.

_{s. auch Bernard Schriek, Informatik mit Java, Band III, S. 110}

• beide werden bedient
• „ich muss etwas geben um etwas zu bekommen“ - Eingabe und Ausgabe
• beide haben einen Mechanismus
• beide sind störanfällig

Beim Colaautomaten hängt die Ausgabe vom Zustand des Automaten bei der Eingabe ab.

Das Verhalten eines Automaten lässt sich in einer Zustandstabelle erfassen und durch ein Zustandsdiagramm veranschaulichen.

Annahme: Der Automat nimmt nur 1€-Münzen an, eine Cola kostet genau 1€. Der Zustand „geladen“ entspricht dabei einem Automaten, in den schon 1€ eingeworfen wurde, ein ungeladener Automat erwartet einen Geldeinwurf.

Die Übergänge werden hier (JFLAP) in der Form Eingabe ; Ausgabe beschriftet (eine andere Notation wäre Eingabe / Ausgabe). Wird nichts ausgegeben, kann das Ausgabefeld auch leer gelassen werden, dann würde anstat - ein für die nicht definierte Ausgabefunktion erscheinen.

Ein endlicher Automat A lässt sich als Sechstupel beschreiben: ¹⁾

Die Symbole stehen dabei im Einzelne für die folgenden Eigenschaften des Automaten:

• : endliche Menge der Zustände, im Beispiel Colaautomat = {ungeladen, geladen}
• : endliche Menge der Eingaben, im Beispiel = {1€, Cola ausgeben, Geld zurück}
• : endliche Menge der Ausgaben, im Beispiel = {1€, Cola}
• x : Übergangsfunktion, die aus einer Zustands-Eingabekombination den Folgezustand ermittelt, z.B. (ungeladen, 1€) = geladen oder (geladen, Cola ausgeben) = ungeladen
• x : Ausgabefunktion, die aus einer Zustands-Eingabekombination die eindeutige Ausgabe ermittelt, z.B. (geladen, Cola ausgeben) = Cola
• : Anfangszustand, wird im Beispiel festgelegt auf = ungeladen

Transduktoren liefern Ausgabe. Beim Mealy-Automaten hängt die Ausgabe vom durchlaufenen Zustandswechsel ab.²⁾

Q = {q0, q1}, = {0, 1}, = {0,1}

(hier steht | für 'oder')

Q = {q0}, = {0, 1}, = {0,1}, , ,

Q = {q0, q1}, = {0, 1}, = {f,w}, Umwandlungsregeln: 0 → f 1 → w

Q = {q0, q1, q2, q3}, = {a, b, c, d}, = {a, b, c, d}, Umwandlungsregeln: a → b, b → c, c → d, d → a

Q = {q0, q1, q2}, = {0, 1}, = {0,1},

und siehe Tabelle

Q = {q0, q1, q2, q3}, = {0, 1, 2}, = {0,1, 2, 3, 4}, Beispiele: 01 → 1 22 → 4

Q = {q0, q1, q2, q3, q4), = {0, 1, 2, 3},

= {verschiedene Worte/Satzfragmente, s. Tabelle und Automat}, Übergänge: s. Tabelle

Q = {q0, q1, q2, q3}, = {0, 1}, = {h, t},

• Suche nach der Schatzinsel³⁾
  Q = {q0, q1, q2, q3, q4, q5, q6} „Inseln“, = {A, B}, Endzustand: q4 (nach unserer Nummerierung)
  Beispiele für :

• Alternative Schatzinselkarte
  
• Bedingungen für Eingabeworte finden