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).
Warum darf ein Automat „raten“? Der nichtdeterministische endliche Automat (NFA) darf bei einem Symbol mehrere Wege gleichzeitig verfolgen. Das macht ihn oft viel kompakter als einen DFA, ohne mehr Sprachen erkennen zu können. Klausurpflicht in 8/8 Theo-Inf-Modulen, meist mit der Potenzmengenkonstruktion.
Klausur-Tipp: Beginne die Potenzmengenkonstruktion immer mit {q₀} und arbeite die neu entstehenden Mengen ab, bis keine neue mehr auftaucht. Markiere jede Menge als akzeptierend, sobald sie einen NFA-Endzustand enthält.
Anmelden, um den Fortschritt zu speichern.
Nächster Schritt
Aktives Abrufen festigt Wissen schneller als nochmal lesen.
Warum darf ein Automat „raten“? Der nichtdeterministische endliche Automat (NFA) darf bei einem Symbol mehrere Wege gleichzeitig verfolgen. Das macht ihn oft viel kompakter als einen DFA, ohne mehr Sprachen erkennen zu können. Klausurpflicht in 8/8 Theo-Inf-Modulen, meist mit der Potenzmengenkonstruktion.
Ein NFA darf für ein Symbol keinen, einen oder mehrere Übergänge haben. Er akzeptiert ein Wort, wenn es MINDESTENS EINEN Pfad gibt, der in einem akzeptierenden Zustand endet.
Ein NFA ist ebenfalls ein 5-Tupel M = (Q, Σ, δ, q₀, F), aber die Übergangsfunktion liefert eine MENGE von Zuständen:
δ: Q × Σ → P(Q) (Potenzmenge von Q)
Aus einem Zustand kann ein Symbol also zu mehreren Zuständen führen (Nichtdeterminismus) oder zu gar keinem (leere Menge).
| DFA | NFA | |
|---|---|---|
| Übergänge pro Zustand+Symbol | genau einer | keiner, einer oder mehrere |
| δ liefert | einen Zustand | eine Zustandsmenge |
| Verarbeitung | ein eindeutiger Pfad | mehrere mögliche Pfade |
| Akzeptanz | Pfad endet in F | EIN Pfad endet in F |
| ε-Übergänge | nein | beim ε-NFA erlaubt |
Manche NFAs erlauben ε-Übergänge: Zustandswechsel OHNE ein Symbol zu lesen. Auch ε-NFAs erkennen nur reguläre Sprachen, sie sind eine Bequemlichkeit beim Konstruieren (z.B. bei der Thompson-Konstruktion aus regulären Ausdrücken).
Ein Wort wird akzeptiert, wenn es UNTER ALLEN möglichen Pfaden mindestens einen gibt, der in einem akzeptierenden Zustand endet. Man kann sich das als parallele Verfolgung aller Möglichkeiten vorstellen oder als „glückliches Raten“.
Zu jedem NFA gibt es einen DFA, der dieselbe Sprache erkennt (und umgekehrt). Beide erkennen genau die regulären Sprachen.
Der NFA ist also nicht „stärker“, nur oft kompakter. Die Umwandlung leistet die Potenzmengenkonstruktion.
Sie macht aus einem NFA einen äquivalenten DFA. Die Grundidee: jeder DFA-Zustand ist eine Menge von NFA-Zuständen (alle, in denen der NFA gerade gleichzeitig sein könnte).
Im schlimmsten Fall entstehen 2ⁿ DFA-Zustände (alle Teilmengen von n NFA-Zuständen), meist deutlich weniger.
1. NFA: δ liefert eine ZustandsMENGE (Potenzmenge), DFA: einen Zustand.
2. NFA akzeptiert, wenn EIN Pfad in F endet.
3. NFA und DFA erkennen dieselbe Sprachklasse: regulär.
4. Potenzmengenkonstruktion: DFA-Zustände = Mengen von NFA-Zuständen.
5. DFA-Startmenge = {q₀}, akzeptierend = Menge enthält einen NFA-Endzustand.
6. Worst Case 2ⁿ DFA-Zustände, real oft weniger (nur erreichbare Mengen).
1. NFA für mächtiger halten als DFA. Beide erkennen exakt die regulären Sprachen. Der NFA ist nur kompakter, nicht stärker.
2. Alle 2ⁿ Mengen aufbauen. Man konstruiert NUR die vom Startzustand aus erreichbaren Mengen, nicht alle Teilmengen.
3. Akzeptanz „alle Pfade“ verlangen. Es reicht EIN akzeptierender Pfad. (Das „für alle“ wäre ein anderer Automatentyp.)
4. Leere Menge vergessen. Führt ein Symbol nirgendwohin, ist der Folge-DFA-Zustand die leere Menge ∅ (ein nicht-akzeptierender Fangzustand).
5. ε-Hülle übersehen. Bei ε-NFAs muss man vor und nach jedem Schritt alle per ε erreichbaren Zustände hinzunehmen.
6. NFA-Übergangstabelle wie beim DFA lesen. Beim NFA steht in jeder Zelle eine Menge, nicht ein einzelner Zustand.
Im ersten Tab siehst du einen NFA für „endet auf ab“ mit dem typischen nichtdeterministischen a-Übergang aus q0. Im zweiten Tab baust du Schritt für Schritt die Potenzmengenkonstruktion auf: jede Zeile ist ein DFA-Zustand (eine Menge von NFA-Zuständen) mit seinen Übergängen.
Interaktive Visualisierung
Interaktive Komponente: probiere sie im Topic-Player oben aus.
Klausur-Tipp: Beginne die Potenzmengenkonstruktion immer mit {q₀} und arbeite die neu entstehenden Mengen ab, bis keine neue mehr auftaucht. Markiere jede Menge als akzeptierend, sobald sie einen NFA-Endzustand enthält.
6 Aufgaben zu Nichtdeterminismus und Umwandlung.
Klausurfragen mit Lösungen (6)
Antwort: Eine Menge von Folgezuständen (Potenzmenge)
Erklärung: Beim NFA liefert δ: Q × Σ → P(Q) eine MENGE von Zuständen (Potenzmenge). Aus einem Zustand kann ein Symbol zu mehreren Zuständen führen (Nichtdeterminismus) oder zu keinem (leere Menge). Beim DFA liefert δ dagegen genau einen Zustand. Klausur-Kernunterschied.
Antwort: Wenn MINDESTENS EIN Pfad in einem akzeptierenden Zustand endet
Erklärung: Ein NFA akzeptiert, wenn es MINDESTENS EINEN Pfad gibt, der in einem akzeptierenden Zustand endet (existenzielle Akzeptanz). Man kann es sich als „glückliches Raten“ oder paralleles Verfolgen aller Möglichkeiten vorstellen. „Alle Pfade“ zu verlangen wäre ein anderes Akzeptanzmodell. Klausur-Grundregel.
Zuordnungen:
Erklärung: DFA: deterministisch, δ liefert genau einen Zustand, ein Übergang pro Symbol. NFA: δ liefert eine Menge, mehrere/keine Übergänge möglich, ε-Übergänge (beim ε-NFA) erlaubt. Beide erkennen aber dieselbe Sprachklasse. Klausur-Pflicht-Zuordnung.
Typ: Zuordnung
Antwort: Die Menge {q₀}
Erklärung: Der Startzustand des konstruierten DFA ist die Menge {q₀}, die nur den NFA-Startzustand enthält (bei ε-NFA zusätzlich dessen ε-Hülle). Von dort aus werden die erreichbaren Mengen aufgebaut. Klausur-Konstruktionsschritt.
Antwort: Falsch
Erklärung: FALSCH. NFA und DFA sind gleich mächtig: beide erkennen genau die regulären Sprachen. Zu jedem NFA gibt es per Potenzmengenkonstruktion einen äquivalenten DFA. Der NFA ist nur oft kompakter (weniger Zustände), nicht ausdrucksstärker. Klausur-Stolperstein.
Typ: Wahr/Falsch
Antwort: 2ⁿ
Erklärung: Im schlimmsten Fall 2ⁿ, denn die DFA-Zustände sind Teilmengen der n NFA-Zustände, und es gibt 2ⁿ Teilmengen. In der Praxis entstehen meist viel weniger, weil nur die vom Start aus erreichbaren Mengen konstruiert werden. Diese mögliche exponentielle Vergrößerung ist der Preis für die Determinisierung. Klausur-Transferfrage.
6 Klausur-Fragen zu Äquivalenz und Potenzmengenkonstruktion.
Klausurfragen mit Lösungen (6)
Antwort: Potenzmengenkonstruktion (Subset-Konstruktion)
Erklärung: Die Potenzmengenkonstruktion (engl. subset construction) wandelt einen NFA in einen äquivalenten DFA um, dessen Zustände Mengen von NFA-Zuständen sind. Das Pumping-Lemma beweist Nicht-Regularität, die Thompson-Konstruktion macht aus Regex einen NFA, die Minimierung verkleinert einen DFA. Klausur-Verfahrenszuordnung.
Antwort: Ein Zustandswechsel, ohne ein Symbol zu lesen
Erklärung: Ein ε-Übergang (epsilon) wechselt den Zustand, OHNE ein Eingabesymbol zu lesen. ε-NFAs sind eine Bequemlichkeit beim Konstruieren (z.B. Thompson-Konstruktion aus regulären Ausdrücken), erkennen aber ebenfalls nur reguläre Sprachen. Klausur-Begriff.
Zuordnungen:
Erklärung: Bei a führt q0 nach {q0, q1} (Nichtdeterminismus), q1 und q2 haben keinen a-Übergang. Daher liefert a aus jeder Menge, die q0 enthält, stets {q0, q1}. Akzeptierend ist nur {q0, q2}, weil sie den NFA-Endzustand q2 enthält. Klausur-Konstruktion.
Typ: Zuordnung
Antwort: Wenn die Menge mindestens einen akzeptierenden NFA-Zustand enthält
Erklärung: Eine DFA-Zustandsmenge ist akzeptierend, sobald sie MINDESTENS EINEN akzeptierenden NFA-Zustand enthält. Das spiegelt die NFA-Akzeptanz wider (ein akzeptierender Pfad reicht). Die leere Menge ∅ ist nie akzeptierend (Fangzustand). Klausur-Regel.
Antwort: Wahr
Erklärung: RICHTIG. NFAs sind häufig deutlich kompakter, weil sie „raten“ dürfen. Die Determinisierung per Potenzmengenkonstruktion kann die Zustandszahl bis auf 2ⁿ aufblähen. Das ist der Hauptgrund, warum man NFAs überhaupt nutzt: einfacher zu konstruieren. Klausur-Vorteil.
Typ: Wahr/Falsch
Antwort: Weil nur die vom Startzustand aus erreichbaren Zustandsmengen konstruiert werden
Erklärung: Man konstruiert nur die ERREICHBAREN Zustandsmengen, beginnend bei {q₀}. Die meisten der 2ⁿ theoretisch möglichen Teilmengen treten nie auf. Die 2ⁿ-Schranke ist ein Worst Case, der nur bei speziell konstruierten NFAs annähernd erreicht wird. Klausur-Transferfrage.