Endliche Automaten Oberstufe

Ein Getränkeautomat, eine Ampel, ein Türschloss mit Zahlencode: Sie alle befinden sich immer in einem Zustand und wechseln je nach Eingabe in einen anderen. Genau das ist die Idee eines Automaten.

Beispiel: Gerade Anzahl Einsen

Ein Automat soll prüfen, ob ein Binärwort eine gerade Anzahl von Einsen enthält (0110 ✅, 0100 ❌).

• G = „bisher gerade viele Einsen“ (Startzustand, Endzustand: doppelter Kreis)
• U = „bisher ungerade viele Einsen“
• Bei 1 wechselt der Zustand, bei 0 bleibt er.

Wörter prüfen

Der Automat liest das Wort Zeichen für Zeichen und folgt den Pfeilen. Ist er am Ende in einem Endzustand, wird das Wort akzeptiert.

Wort 0110:   G ─0→ G ─1→ U ─1→ G ─0→ G    Endzustand ✅ akzeptiert
Wort 0100:   G ─0→ G ─1→ U ─0→ U ─0→ U    kein Endzustand ❌ abgelehnt

Formale Definition

Merke: Deterministischer endlicher Automat (DEA)

Ein DEA ist ein 5-Tupel A = (Q, Σ, δ, q₀, F) mit

• Q: endliche Menge von Zuständen, hier
• Σ: Eingabealphabet, hier
• δ: Überführungsfunktion Q × Σ → Q, sie sagt, wohin ein Zeichen führt
• q₀ ∈ Q: Startzustand, hier G
• F ⊆ Q: Menge der Endzustände, hier

Deterministisch heißt: Aus jedem Zustand führt für jedes Zeichen genau ein Pfeil.

Die Überführungsfunktion als Tabelle:

δ	0	1
→ G (Ende)	G	U
U	U	G

Fehlerzustand

Soll ein Wort sofort ungültig sein (z. B. eine führende Null bei Binärzahlen), führt man einen Fehlerzustand (Falle) ein, aus dem kein Weg mehr herausführt.

Aufgaben

1. Entwirf einen DEA über {a, b}, der alle Wörter akzeptiert, die mit ab enden.
2. Entwirf einen DEA, der Binärzahlen ohne führende Nullen akzeptiert (0, 1, 10, 110, aber nicht 01).
3. Ein Roboter kennt die Befehle v (vor) und d (drehen). Nach zwei d direkt hintereinander soll er stoppen. Modelliere das als Automat.

Zeichne und teste deine Automaten mit FLACI.

Grenzen endlicher Automaten

Endliche Automaten haben kein Gedächtnis

Ein endlicher Automat „merkt“ sich nur seinen aktuellen Zustand, und davon gibt es endlich viele. Deshalb kann er z. B. Palindrome (abba, racecar) nicht erkennen: Er müsste sich die gesamte erste Hälfte des Wortes merken, die beliebig lang sein kann. Auch „gleich viele a wie b“ oder korrekte Klammerungen schafft er nicht.

Weitere Automatentypen Lk

Automat	Besonderheit	erkennt
DEA	genau ein Folgezustand	reguläre Sprachen
NEA (nichtdeterministisch)	mehrere Folgezustände möglich; ist gleich mächtig wie ein DEA	reguläre Sprachen
Kellerautomat	zusätzlich ein Stapelspeicher (Keller)	kontextfreie Sprachen, z. B. Klammerungen
Turingmaschine	unendliches Band, auf dem gelesen und geschrieben wird	alles Berechenbare (→ Grenzen der Berechenbarkeit)
Registermaschine	Speicherzellen und einfache Befehle, ähnlich einem echten Rechner	gleich mächtig wie die Turingmaschine