Alle Tabs der Lerneinheit (Erklärung · Interaktiv verstehen · Praxis-Übung · Klausur-Quiz) als durchgehender Text. Ideal zum Wiederholen vor der Klausur, und für Suchmaschinen wie Google, Bing und KI-Suche (ChatGPT, Perplexity).
Erklärung
Endliche Automaten (DFA)
Wie prüft ein Programm, ob eine Eingabe einem Muster entspricht, mit minimalem Speicher? Mit einem endlichen Automaten: einer der einfachsten Rechenmaschinen der Theoretischen Informatik. Er hat nur endlich viele Zustände und kein zusätzliches Gedächtnis. Klausurpflicht in 8/8 Theo-Inf-Modulen, fast immer als Konstruktions-Aufgabe.
Die Idee in einem Satz
Ein deterministischer endlicher Automat (DFA) liest ein Wort Zeichen für Zeichen und wechselt dabei zwischen endlich vielen Zuständen. Endet er in einem akzeptierenden Zustand, gehört das Wort zur Sprache.
Die formale Definition (5-Tupel)
Ein DFA ist ein Tupel M = (Q, Σ, δ, q₀, F):
| Symbol | Bedeutung |
|---|---|
| Q | endliche Menge von Zuständen |
| Σ (Sigma) | endliches Eingabe-Alphabet |
| δ (delta) | Übergangsfunktion δ: Q × Σ → Q |
| q₀ | Startzustand (q₀ ∈ Q) |
| F | Menge akzeptierender (End-)Zustände (F ⊆ Q) |
Deterministisch und vollständig
Das "D" in DFA steht für deterministisch:
Für jeden Zustand und jedes Eingabesymbol gibt es GENAU EINEN Folgezustand.
Die Übergangsfunktion δ ist also eine totale Funktion: kein Übergang fehlt, keiner ist doppelt. Daher ist der Weg durch den Automaten für ein gegebenes Wort eindeutig festgelegt.
Wann wird ein Wort akzeptiert?
- Starte in q₀.
- Lies das Wort Zeichen für Zeichen, folge bei jedem Zeichen dem Übergang.
- Ist der Zustand nach dem letzten Zeichen in F (akzeptierend), wird das Wort akzeptiert, sonst abgelehnt.
Die Menge aller akzeptierten Wörter ist die vom Automaten erkannte Sprache L(M).
Das Zustandsdiagramm
| Notation | Bedeutung |
|---|---|
| Kreis | ein Zustand |
| Pfeil von außen | Startzustand q₀ |
| Doppelkreis | akzeptierender Zustand (in F) |
| beschrifteter Pfeil | Übergang δ (Symbol als Label) |
| Schleife am Zustand | Übergang auf sich selbst |
Beispiel: „Wörter, die auf ab enden“
3 Zustände: q0 (Start), q1 ("zuletzt a"), q2 ("zuletzt ab", akzeptierend). Liest der Automat ein b nach einem a, landet er in q2. Kommt danach noch ein Zeichen, verlässt er q2 wieder. Akzeptiert wird nur, wenn die Verarbeitung in q2 endet.
DFA und reguläre Sprachen
Eine Sprache ist genau dann regulär, wenn es einen DFA gibt, der sie erkennt.
DFAs, NFAs und reguläre Ausdrücke beschreiben dieselbe Sprachklasse: die regulären Sprachen (Typ 3 der Chomsky-Hierarchie). Das ist der Kern der ersten Hälfte jeder Theo-Inf-Vorlesung.
Klausur-Faustregeln
1. DFA = 5-Tupel (Q, Σ, δ, q₀, F). Auswendig.
2. Deterministisch + vollständig: pro Zustand und Symbol genau ein Übergang.
3. Akzeptiert = Verarbeitung endet in einem Zustand aus F.
4. Startzustand: Pfeil von außen. Akzeptierend: Doppelkreis.
5. L(M) = Menge aller akzeptierten Wörter.
6. DFA erkennt genau die regulären Sprachen.
Häufige Stolpersteine
1. Akzeptanz am Zwischenzustand annehmen. Es zählt NUR der Zustand NACH dem letzten Zeichen, nicht ob man unterwegs mal akzeptierend war.
2. Übergänge vergessen (Unvollständigkeit). Ein DFA braucht für JEDES Symbol in JEDEM Zustand einen Übergang. Oft hilft ein Fang-/Müllzustand für unerwünschte Eingaben.
3. Determinismus verletzen. Zwei Übergänge mit demselben Symbol aus einem Zustand sind im DFA verboten (das wäre ein NFA).
4. Das leere Wort ε falsch behandeln. Für ε endet die Verarbeitung sofort in q₀. Akzeptiert wird ε genau dann, wenn q₀ akzeptierend ist.
5. Start- und Endzustand verwechseln. Der Startzustand kann auch akzeptierend sein (beide Markierungen zugleich möglich).
6. Zustände als Speicher überladen. Ein DFA hat nur seine endlich vielen Zustände als Gedächtnis, er kann z.B. nicht beliebig viele Zeichen zählen (das braucht das Pumping-Lemma als Grenze).
Interaktiv verstehen
DFA, interaktiv
Wähle einen der beiden Beispiel-Automaten und ein Test-Wort. Gehe Schritt für Schritt durch die Verarbeitung: der aktuelle Zustand leuchtet im Zustandsdiagramm, das gerade gelesene Symbol wird im Wort markiert, und am Ende siehst du, ob der Automat akzeptiert oder ablehnt.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Übe, für eine gegebene Sprache selbst einen DFA zu zeichnen. Frage dich pro Zustand: „Was muss ich mir bis hierher gemerkt haben?“ Jeder Zustand steht für eine Eigenschaft des bisher gelesenen Wortes.
Praxis-Übung
DFA, Praxis-Übung
6 Aufgaben zu Definition, Akzeptanz und Konstruktion.
Klausurfragen mit Lösungen (6)
- F1.Wofür steht das „D“ in DFA?
Antwort: Deterministisch (pro Zustand und Symbol genau ein Übergang)
Erklärung: DFA = Deterministic Finite Automaton (deterministischer endlicher Automat). Deterministisch heißt: für jeden Zustand und jedes Eingabesymbol gibt es genau einen Folgezustand. Der Weg durch den Automaten ist dadurch für jedes Wort eindeutig. Klausur-Grundbegriff.
- F2.Aus welchen fünf Komponenten besteht ein DFA (5-Tupel)?
Antwort: Q, Σ, δ, q₀, F
Erklärung: Ein DFA ist das 5-Tupel M = (Q, Σ, δ, q₀, F): Q = Zustände, Σ = Eingabe-Alphabet, δ = Übergangsfunktion (Q × Σ → Q), q₀ = Startzustand, F = akzeptierende Zustände. Ein Stack gehört zum Kellerautomaten, ein Band zur Turing-Maschine. Klausur-Pflichtdefinition.
- F3.Ordne die DFA-Komponente ihrer Bedeutung zu.
Zuordnungen:
- Q → Menge der Zustände
- Σ → Eingabe-Alphabet
- δ → Übergangsfunktion Q × Σ → Q
- F → akzeptierende Zustände
Erklärung: Q = Zustandsmenge, Σ (Sigma) = Eingabe-Alphabet, δ (delta) = Übergangsfunktion (nimmt Zustand + Symbol, liefert Folgezustand), F = Menge der akzeptierenden Endzustände. q₀ (nicht abgefragt) ist der Startzustand. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
- F4.Ein DFA akzeptiert ein Wort, wenn er während der Verarbeitung mindestens einmal einen akzeptierenden Zustand besucht.
Antwort: Falsch
Erklärung: FALSCH. Es zählt NUR der Zustand NACH dem letzten gelesenen Zeichen. Ein Wort wird akzeptiert, wenn die Verarbeitung in einem akzeptierenden Zustand ENDET, nicht ob unterwegs einer besucht wurde. Klassischer Klausur-Stolperstein.
Typ: Wahr/Falsch
- F5.Ein DFA mit Σ = {a, b} hat einen Zustand q. Wie viele ausgehende Übergänge muss q haben?
Antwort: Genau zwei (einen pro Symbol)
Erklärung: Ein DFA ist deterministisch UND vollständig: für JEDES Symbol des Alphabets braucht jeder Zustand genau einen Übergang. Bei Σ = {a, b} also genau zwei ausgehende Übergänge pro Zustand (einer für a, einer für b). Fehlt einer, ist es kein vollständiger DFA. Klausur-Regel.
- F6.Der DFA „endet auf ab“ verarbeitet das Wort „aba“. Wird es akzeptiert?
Antwort: Nein, weil es nicht auf ab endet (es endet auf a)
Erklärung: Das Wort „aba“ endet auf „ba“, nicht auf „ab“. Verarbeitung: q0 -a-> q1 -b-> q2 -a-> q1. Endzustand ist q1 (nicht akzeptierend), also wird abgelehnt. Dass „ab“ als Teilwort vorkommt, reicht nicht, der Automat verlangt, dass das Wort AUF ab endet. Klausur-Verarbeitungsaufgabe.
Klausur-Quiz
DFA, Klausur-Quiz
6 Klausur-Fragen zu Akzeptanz, regulären Sprachen und Konstruktion.
Klausurfragen mit Lösungen (6)
- F1.Welche Sprachklasse erkennen genau die endlichen Automaten?
Antwort: Die regulären Sprachen
Erklärung: Endliche Automaten (DFA und NFA) erkennen genau die regulären Sprachen (Typ 3 der Chomsky-Hierarchie). Kontextfreie Sprachen brauchen Kellerautomaten, allgemeinere Sprachen die Turing-Maschine. DFA, NFA und reguläre Ausdrücke sind in ihrer Ausdrucksstärke äquivalent. Klausur-Kernaussage.
- F2.Wie wird im Zustandsdiagramm ein akzeptierender Zustand dargestellt?
Antwort: Als Doppelkreis
Erklärung: Akzeptierende Zustände (aus F) werden als Doppelkreis gezeichnet. Der Startzustand bekommt einen Pfeil von außen. Beide Markierungen können auf demselben Zustand zusammenfallen (Startzustand ist akzeptierend). Klausur-Notation.
- F3.Ordne das Wort dem Ergebnis im DFA „gerade Anzahl a“ zu.
Zuordnungen:
- aa → akzeptiert (2 a)
- aba → abgelehnt (1 a... plus 1 a = 2? nein: 2 a)
- ε (leer) → akzeptiert (0 a, gerade)
- aab → akzeptiert (2 a)
Erklärung: Der DFA akzeptiert Wörter mit gerader Anzahl a. aa = 2 a (gerade) akzeptiert. aab = 2 a akzeptiert. ε = 0 a (gerade) akzeptiert, weil der Startzustand akzeptierend ist. aba = 2 a, also ebenfalls gerade und akzeptiert (Vorsicht: hier zählt nur die Anzahl der a, das b ist irrelevant). Klausur-Verarbeitung.
Typ: Zuordnung
- F4.Warum hilft bei der DFA-Konstruktion oft ein „Fang-“ oder „Müllzustand“?
Antwort: Er nimmt alle unerwünschten Eingaben auf und macht den DFA vollständig
Erklärung: Ein Fang-/Müllzustand (engl. trap/dead state) ist ein nicht-akzeptierender Zustand, der alle Eingaben auf sich selbst abbildet. Er fängt unerwünschte Präfixe ab und sorgt dafür, dass der DFA vollständig ist (jeder Zustand hat für jedes Symbol einen Übergang). Klausur-Konstruktionstrick.
- F5.Der Startzustand eines DFA kann gleichzeitig ein akzeptierender Zustand sein.
Antwort: Wahr
Erklärung: RICHTIG. Start- und Endzustands-Eigenschaft sind unabhängig. Ist der Startzustand akzeptierend, dann akzeptiert der DFA das leere Wort ε (die Verarbeitung von ε endet sofort im Startzustand). Beispiel: DFA für „gerade Anzahl a“ akzeptiert ε. Klausur-Detail.
Typ: Wahr/Falsch
- F6.Welche der folgenden Sprachen kann ein DFA NICHT erkennen?
Antwort: Wörter der Form aⁿbⁿ (gleich viele a wie b)
Erklärung: aⁿbⁿ (gleich viele a wie b) ist NICHT regulär: ein DFA müsste sich beliebig große Zahlen n merken, hat aber nur endlich viele Zustände. Das beweist man mit dem Pumping-Lemma. Die anderen drei Sprachen sind regulär (endlich viel zu merken: Anfang, Längen-Parität, Teilwort-Suche). Klausur-Transferfrage zur Grenze regulärer Sprachen.
