NFA zu DFA Zustandsexplosion
Maximale Zustandsanzahl des durch Potenzmengenkonstruktion erzeugten DFA: MaxDFAZustaende = 2^NFAZustaende.
NFA zu DFA Zustandsexplosion berechnen
Maximale Zustandsanzahl des durch Potenzmengenkonstruktion erzeugten DFA: MaxDFAZustaende = 2^NFAZustaende.
- MaxDFAZustaende — Max. DFA-Zustände
- NFAZustaende — NFA-Zustände
Worum geht es?
Die Potenzmengenkonstruktion (Subset Construction) verwandelt einen NFA mit |Q| Zuständen in einen sprachäquivalenten DFA. Da ein DFA-Zustand jeder Teilmenge der NFA-Zustandsmenge entsprechen kann, gibt es im Worst Case
MaxDFAZustaende = 2^|Q_NFA|
mögliche DFA-Zustände. Diese exponentielle Schranke heißt Zustandsexplosion.
In der Praxis liegt die tatsächliche Zustandsanzahl meist deutlich darunter, weil viele Teilmengen unerreichbar sind oder durch DFA-Minimierung verschmelzen. Für Worst-Case-Analysen, Generator-Quotas und sicherheitsrelevante Lexer (z. B. ReDoS-Härtung) ist die obere Schranke aber maßgeblich.
Die Formel
MaxDFAZustaende = 2^NFAZustaende
Umstellung:
NFAZustaende = log₂(MaxDFAZustaende)Die Variablen
| Symbol | Bedeutung | Einheit | Erklärung |
|---|---|---|---|
| NFAZustaende | NFA-Zustände | — | Anzahl Zustände |Q| im Ausgangs-NFA. |
| MaxDFAZustaende | Max. DFA-Zustände | — | Worst-Case-Zustandsanzahl im erzeugten DFA. |
Minimal-Beispiel
NFA mit 5 Zuständen:
MaxDFAZustaende = 2^5
= 32Praxis-Beispiele
Beispiel 1 — Regex-Lexer
Ein regex-basierter Lexer-NFA hat 20 Zustände:
MaxDFAZustaende = 2^20
= 1 048 576Beispiel 2 — NFA-Größe aus DFA-Schranke
Ein Werkzeug meldet maximal 1024 DFA-Zustände:
NFAZustaende = log₂(1024)
= 10Beispiel 3 — Sicherheitsanalyse
Härtungsschwelle: ein gegnerischer Regex erzeugt einen NFA mit 32 Zuständen:
MaxDFAZustaende = 2^32
= 4 294 967 296 ≈ 4,3 · 10⁹
→ DFA-Materialisierung muss begrenzt werden (Lazy DFA).