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
NFA und Potenzmengenkonstruktion
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.
Die Idee in einem Satz
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.
Die formale Definition
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).
Der Unterschied zum DFA
| 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 |
ε-Übergänge (epsilon)
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).
Akzeptanz beim NFA
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“.
NFA und DFA sind gleich mächtig
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.
Die Potenzmengenkonstruktion (Subset-Konstruktion)
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).
- Startzustand des DFA: die Menge {q₀} (bei ε-NFA: ε-Hülle von q₀).
- Übergang: für eine Menge S und ein Symbol a ist der Folgezustand die Vereinigung aller δ(q, a) für q ∈ S.
- Nur die vom Start aus erreichbaren Mengen werden erzeugt.
- Akzeptierend ist jede Menge, die mindestens einen akzeptierenden NFA-Zustand enthält.
Im schlimmsten Fall entstehen 2ⁿ DFA-Zustände (alle Teilmengen von n NFA-Zuständen), meist deutlich weniger.
Klausur-Faustregeln
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).
Häufige Stolpersteine
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.
Interaktiv verstehen
NFA, interaktiv
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.
Praxis-Übung
NFA, Praxis-Übung
6 Aufgaben zu Nichtdeterminismus und Umwandlung.
Klausurfragen mit Lösungen (6)
- F1.Was liefert die Übergangsfunktion δ eines NFA?
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.
- F2.Wann akzeptiert ein NFA ein Eingabewort?
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.
- F3.Ordne den Aspekt dem richtigen Automatentyp zu.
Zuordnungen:
- δ liefert einen Zustand → DFA
- δ liefert eine Zustandsmenge → NFA
- ε-Übergänge möglich → NFA (ε-NFA)
- genau ein Übergang pro Symbol → DFA
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
- F4.Was ist der Startzustand des DFA bei der Potenzmengenkonstruktion (ohne ε)?
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.
- F5.Ein NFA kann Sprachen erkennen, die kein DFA erkennen kann.
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
- F6.Ein NFA hat n Zustände. Wie viele Zustände kann der per Potenzmengenkonstruktion erzeugte DFA im schlimmsten Fall haben?
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.
Klausur-Quiz
NFA, Klausur-Quiz
6 Klausur-Fragen zu Äquivalenz und Potenzmengenkonstruktion.
Klausurfragen mit Lösungen (6)
- F1.Welches Verfahren wandelt einen NFA in einen äquivalenten DFA um?
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.
- F2.Was ist ein ε-Übergang in einem NFA?
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.
- F3.NFA „endet auf ab“: ordne die Zustandsmenge ihrem Übergang bei a zu.
Zuordnungen:
- {q0} → {q0, q1}
- {q0, q1} → {q0, q1}
- {q0, q2} → {q0, q1}
- akzeptierend ist → {q0, q2}
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
- F4.Wann ist ein DFA-Zustand (eine Zustandsmenge) in der Potenzmengenkonstruktion akzeptierend?
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.
- F5.Ein NFA ist oft kompakter (hat weniger Zustände) als der äquivalente DFA für dieselbe Sprache.
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
- F6.Warum erzeugt die Potenzmengenkonstruktion in der Praxis meist deutlich weniger als 2ⁿ Zustände?
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.
