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).
Teil 1·Erklärung
Diese Lerneinheit wurde für typische Bachelor-Klausuren konzipiert. So prüfen wir · Fehler entdeckt? Melde ihn uns oder markiere die fragliche Stelle direkt im Text oben.
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).
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.
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.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
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.
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.
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) |
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.
Die Menge aller akzeptierten Wörter ist die vom Automaten erkannte Sprache L(M).
| 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 |
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.
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.
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.
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).
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.
6 Aufgaben zu Definition, Akzeptanz und Konstruktion.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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
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.
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.
6 Klausur-Fragen zu Akzeptanz, regulären Sprachen und Konstruktion.
Klausurfragen mit Lösungen (6)
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.
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.
Zuordnungen:
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
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.
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
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.