MINT lernen

Automaten & Sprachen im Abitur

Drei Modelle, eine Notation: Wer die Anlage sicher liest, holt die schnellen Punkte — und hat Zeit für den Entwurf.

1

Automaten in der Anlage

Die Anlage zum Abitur legt die Notation fest — genau so werden Aufgaben gestellt und Lösungen bewertet.

  • Endlicher Automat:Eingabealphabet Σ und Zustandsgraph; Endzustände mit doppeltem Rand. Vollständig angeben — den Fehlerzustand nur weglassen, wenn im Text darauf hingewiesen wird.
  • Mealy-Automat:Σ, Ausgabealphabet Ω und vollständiger Graph; Übergang e / a, auch Wörter als Ausgabe, ε für keine Ausgabe.
  • Kellerautomat:Σ und Kelleralphabet Γ; Übergang (X,e):W — X ist das oberste Kellerzeichen und wird entfernt, W wird abgelegt, das rechte Zeichen zuerst.
  • Vorbelegung und ε:zu Beginn liegt # im Keller; ε-Übergänge sind erlaubt, aber nicht neben einem Übergang mit demselben obersten Kellerzeichen.
  • Akzeptieren:Eingabe vollständig verarbeitet und Endzustand erreicht.

Wickle den Lauf des Kellerautomaten ab: Ziehe den Griff unter dem Streifen nach rechts (oder Pfeiltasten) — jede Spalte ist eine Konfiguration mit Zustand, gelesenem Zeichen, Übergang in der Notation der Anlage und Keller. Probiere alle vier Wörter.

Den Kellerlauf abwickeln

Halte fest: Genau diesen Streifen verlangt eine Abituraufgabe, wenn nach der Folge der Kellerinhalte gefragt ist — Zustand, Resteingabe und Keller (oben links) nach jedem Schritt. Akzeptiert wird nur, wenn das ganze Wort gelesen ist und der Automat in einem Endzustand steht.

2

Grammatiken und Aufgabenformate

  • Grammatik:Menge N der Nichtterminale, Menge T der Terminale, Startsymbol und Produktionsregeln; Nichtterminale groß, Terminale klein; ε ist zulässig.
  • Ablesen und anwenden:Zustandsfolge, Konfigurationsfolge oder Ableitung zu einem Wort angeben (AFB I).
  • Analysieren:Bedeutung der Zustände oder Nichtterminale erläutern, Sprache in Worten oder als Menge beschreiben (AFB II).
  • Entwerfen:DEA, Mealy- oder Kellerautomat bzw. Grammatik zu einer Sprache entwickeln, DEA ↔ Grammatik umwandeln, in Java implementieren (AFB II–III).
  • Grenzen:begründen, warum kein DEA eine Sprache erkennt — mit dem Schubfachprinzip (AFB III).

Beispiel aus der Anlage:

N = {A, B, S}
T = {1, 2, a, c}
Startsymbol: S
Produktionsregeln:
S → 1A | 2B
A → 1B
B → aS | cS | a | c
Merke

Kellerübergang: (X,e):W — oberstes Zeichen X entfernen, W von rechts nach links ablegen. Akzeptiert wird im Endzustand nach vollständiger Eingabe.

3

Allgemeine Hinweise

Notation wörtlich übernehmen

Eigene Schreibweisen wie „a → A push“ kosten Punkte. Übergänge, Grammatiken und Mealy-Pfeile genau wie in der Anlage notieren.

Konfigurationen als Tabelle

Ein Lauf lässt sich am schnellsten als Tabelle mit Schritt, Zustand, Resteingabe, Keller und Übergang aufschreiben — nichts wird vergessen, alles ist prüfbar.

Vermerk nicht vergessen

Wer Übergänge in den Fehlerzustand weglässt, schreibt es dazu. Beim Kellerautomaten gilt: Passt kein Übergang, wird das Wort abgelehnt.

Videos