Formale Sprachen und Automaten
Der Bereich prüft, ob du Sprachen formal beschreibst, sie durch Automaten oder Grammatiken erkennst und die Grenzen der Entscheidbarkeit einordnest. Erwartet werden DEA/NEA-Konstruktionen, reguläre Ausdrücke und die Chomsky-Hierarchie.
Grundbegriffe
Ein Alphabet Σ ist eine endliche Menge von Zeichen. Ein Wort ist eine endliche Folge von Zeichen, ε das leere Wort. Σ* ist die Menge aller Wörter über Σ, eine Sprache ist eine Teilmenge von Σ*. Operationen: Konkatenation, Vereinigung, Kleene-Stern (*, beliebig oft, auch null Mal), Komplement.
Endliche Automaten
Ein DEA ist ein 5-Tupel (Z, Σ, δ, z₀, E) aus Zustandsmenge, Eingabealphabet, Überführungsfunktion, Startzustand, Endzustandsmenge. Ein NEA erlaubt mehrere Folgezustände und ε-Übergänge; durch Potenzmengenkonstruktion wird er in einen äquivalenten DEA überführt. Nach dem Satz von Kleene beschreiben reguläre Ausdrücke, DEAs und Typ-3-Grammatiken dieselbe Sprachklasse.
Grammatiken und Chomsky-Hierarchie
Eine Grammatik G = (N, T, P, S) erzeugt Wörter durch Ableitung. Typ 3 (regulär): rechts- oder linkslineare Regeln. Typ 2 (kontextfrei): linke Seite ist ein einzelnes Nichtterminal; Kellerautomaten erkennen sie, LL-Parser arbeiten top-down mit Vorausschau. Typ 1 (kontextsensitiv), Typ 0 (uneingeschränkt, Turing-Maschine).
Durchgerechnetes Beispiel
Gesucht: DEA über Σ = {0,1} für alle Wörter, die auf 01 enden.
Zustände: q0 (noch kein passendes Suffix), q1 (zuletzt gelesen: 0), q2 (zuletzt gelesen: 01, Endzustand). Überführungen: q0 –0→ q1, q0 –1→ q0, q1 –0→ q1, q1 –1→ q2, q2 –0→ q1, q2 –1→ q0.
Begründung: Die Zustände merken sich das längste gelesene Suffix, das ein Präfix von 01 ist. Test 1101: q0 –1→ q0 –1→ q0 –0→ q1 –1→ q2, akzeptiert. Test 110: Ende in q1, abgelehnt. Wichtig: „endet mit“ ist nicht „enthält“ – ein DEA für „enthält 01“ hätte einen senkenartigen Endzustand, aus dem es keinen Weg zurück gibt.
Typische Fallen
- „endet mit“ und „enthält“ verwechseln.
- ε-Übergänge beim NEA nicht über die ε-Hülle behandeln.
- Das Pumping-Lemma als hinreichend ansehen: Es ist nur ein notwendiges Kriterium zum Widerlegen von Regularität.
- Beim DEA fehlende Übergänge (vollständige Funktion nötig).
- Typ-3-Grammatik mit gemischt linearer rechter Seite verwechseln.
- Das Halteproblem als entscheidbar annehmen – es ist es nicht; die Leerheit einer DEA-Sprache ist dagegen entscheidbar.