Endliche Automaten
Ein DEA liest ein Wort Zeichen für Zeichen und entscheidet am Ende: angenommen oder abgelehnt. Sein ganzes Gedächtnis ist der aktuelle Zustand.
9.1.1
Der deterministische Automat
- \(\Sigma\): Eingabealphabet; Wort, \(\varepsilon\) = leeres Wort.
- Startpfeil, Endzustände als Doppelkreis.
- Deterministisch und vollständig: je Zustand und Zeichen genau ein Pfeil.
- Fehlerzustand zF darf fehlen — nur mit Vermerk.
9.1.2
Automaten analysieren
- Für jeden Zustand die Bedeutung notieren.
- Testwörter nach Länge: \(\varepsilon\), a, b, aa, …
- Gegenprobe mit Grenzfällen.
9.1.3
Einen DEA entwickeln
- Was muss sich der Automat merken? Jede Antwort ein Zustand.
- Für jeden Zustand und jedes Zeichen einen Übergang.
- Rückweg zum längsten noch passenden Ende.
9.1.4
Automaten implementieren
- Attribut
int zustand, Schleife über die Zeichen. switchüber den Zustand oder Tabelleint[][] delta.- Am Anfang
zustand = 0;— sonst erbt der nächste Aufruf den alten Zustand.
zustand = delta[zustand][spalte(c)];Ein Endzustand unterwegs zählt nicht; aus zF führt kein Weg zurück.
Bedeutung vor Pfeilen
Wer zuerst jedem Zustand eine Bedeutung gibt, findet die Übergänge fast von selbst — und sammelt Begründungspunkte.
Mealy- und Kellerautomaten
Ein Mealy-Automat übersetzt statt zu entscheiden. Ein Kellerautomat bekommt zusätzlich einen Stapel — und kann damit beliebig weit zählen.
9.2.1
Der Mealy-Automat
- \(\Sigma\) Eingabe-, \(\Omega\) Ausgabealphabet.
- Pfeil e / a: e lesen, a ausgeben; \(\varepsilon\) = keine Ausgabe.
- Keine Endzustände, aber vollständig.
9.2.2
Grenzen endlicher Automaten
- \(k\) Zustände → höchstens \(k\) Vorgeschichten unterscheidbar.
- Schubfach: \(a^i\), \(a^j\) im selben Zustand → \(a^ib^i\) und \(a^jb^i\) gleich behandelt.
- Beschränkt zählen geht, unbeschränkt nicht.
9.2.3
Der Kellerautomat
| von | Übergang | nach |
|---|---|---|
| z0 | (#,a):A# | z1 |
| z1 | (A,a):AA | z1 |
| z1 | (A,b):ε | z2 |
| z2 | (A,b):ε | z2 |
| z2 | (#,ε):# | z3 (Ende) |
- Kelleralphabet \(\Gamma\), Vorbelegungszeichen #.
- Übergang (X,e):W: oberstes Zeichen X entfernen, W ablegen — rechtes Zeichen zuerst.
- Akzeptiert: Eingabe gelesen und Endzustand erreicht.
(#,a):A# → A liegt oben9.2.4
Kellerautomaten entwickeln
- Erst den Kellerplan: Was legt welches Zeichen ab, was entfernt es?
- Je Abschnitt des Worts ein Zustand (Phasen).
- (#,ε):# in den Endzustand prüft „Keller leer“.
- ε-Übergang nie neben einem Übergang mit demselben obersten Zeichen.
Das gelesene Kellerzeichen wird entfernt; bei mehreren abgelegten Zeichen wird das rechte zuerst abgelegt, das linke liegt danach oben.
ε ist nicht 0
\(\varepsilon\) heißt: nichts ausgeben, nichts lesen oder nichts ablegen. 0 ist ein echtes Zeichen.
Formale Sprachen und Grammatiken
Grammatiken erzeugen Wörter mit Regeln. Reguläre Grammatiken passen zum DEA, kontextfreie zum Kellerautomaten.
9.3.1
Formale Sprachen
- Wort = endliche Zeichenfolge über \(\Sigma\); Länge \(|w|\).
- \(\Sigma^*\): alle Wörter; Sprache = Teilmenge von \(\Sigma^*\).
- Syntax (Aufbau) vs. Semantik (Bedeutung).
9.3.2
Grammatiken und Ableitungen
T = {a, b}
Startsymbol: S
Produktionsregeln:
S → aA
A → bS | ε
- N (Nichtterminale), T (Terminale), Startsymbol, Produktionsregeln.
- Ableitung \(S\Rightarrow\dots\Rightarrow w\); Satzform = Zwischenschritt.
- Ableitungsbaum: Blätter von links nach rechts = Wort.
9.3.3
Reguläre Grammatiken
- Nur Regeln \(A\to aB\), \(A\to a\), \(A\to\varepsilon\).
- Nichtterminal immer ganz rechts in der Satzform.
- Entwurf: je Information ein Nichtterminal, ε-Regel wo das Wort enden darf.
9.3.4
Reguläre Grammatik und DEA
- Zustand = Nichtterminal, Start = Startsymbol.
- Pfeil \(z\xrightarrow{a}z'\) = Regel \(Z\to aZ'\).
- Endzustand = ε-Regel; \(A\to a\) → neuer Endzustand zE.
9.3.5
Kontextfreie Grammatiken
- Links genau ein Nichtterminal, rechts beliebig.
- \(S\to aSb\mid\varepsilon\) erzeugt \(\{a^nb^n\}\).
- Linksableitung; mehrdeutig = zwei Bäume für ein Wort.
Überblick
Welches Modell für welche Sprache?
| Sprachklasse | Automat | Grammatik |
|---|---|---|
| regulär | DEA | regulär |
| kontextfrei | Kellerautomat | kontextfrei |
- Regulär ⊂ kontextfrei.
- \(\{a^nb^nc^n\}\) ist nicht kontextfrei.
- Endliche Sprachen sind immer regulär.
Ob eine Sprache regulär ist, entscheidet nicht eine einzelne Grammatik — sondern ob es irgendeine reguläre Grammatik (bzw. einen DEA) für sie gibt.
→ ist nicht ⇒
Der Pfeil → steht in Regeln, der Doppelpfeil ⇒ zwischen Satzformen einer Ableitung.
Die Regeln, an denen die Punkte hängen
Was in Klausuren zu Automaten und Sprachen am häufigsten Punkte kostet:
Regel 1 — vollständig oder Vermerk
Beim DEA braucht jeder Zustand für jedes Zeichen einen Pfeil. Wer den Fehlerzustand weglässt, schreibt dazu: „Nicht eingezeichnete Übergänge führen in den Fehlerzustand zF.“
Regel 2 — Notation der Anlage
Grammatik mit N, T, Startsymbol und Produktionsregeln; Kellerübergänge als (X,e):W mit # als Vorbelegung; Mealy-Übergänge als e / a. Genau so steht es in der Anlage — und so wird bewertet.
Regel 3 — Testen und begründen
Zu jedem Entwurf gehören Testwörter mit Grenzfällen (\(\varepsilon\), kürzeste Wörter, knapp falsche Wörter) und bei Grenzen ein vollständiges Schubfach-Argument: Annahme, Schubfach, gleicher Zustand, Widerspruch.