3. Determinismus und Potenzmengenkonstruktion

Thema 3: Determinismus, Potenzmengenkonstruktion - Umwandlung NFA in DFA

1. Determinismus (DFA) vs. Nichtdeterminismus (NFA)

• Deterministischer Endlicher Automat (DFA):

  • Eigenschaft: Für jedes Symbol des Alphabets gibt es genau einen definierten Übergang pro Zustand.

  • Beispiel:

    • Zustand A → (a) → Zustand B

    • Zustand B → (b) → Zustand C

  • Vorteil: Einfacher zu implementieren und zu verstehen.

  • Nachteil: Kann mehr Zustände benötigen als ein NFA.

• Nichtdeterministischer Endlicher Automat (NFA):

  • Eigenschaft: Für ein Eingabesymbol können mehrere Übergänge möglich sein.

  • Beispiel:

    • Zustand A → (a) → Zustand B oder Zustand C

    • Erlaubt auch ε-Übergänge (Übergänge ohne Eingabesymbol).

  • Vorteil: Oft einfacher zu entwerfen.

  • Nachteil: In der Praxis schwerer direkt umzusetzen.

Wichtige Erkenntnis: Jeder NFA kann in einen äquivalenten DFA umgewandelt werden.

---

2. Potenzmengenkonstruktion (Subset Construction)

• Definition: Ein Verfahren, um einen NFA in einen äquivalenten DFA umzuwandeln.

• Grundidee:

  • Jeder Zustand des DFA entspricht einer Menge von Zuständen des NFA.

  • Damit wird der nichtdeterministische Automat in einen deterministischen überführt.

Schritte der Potenzmengenkonstruktion:

1. Startzustand des DFA: Menge aller NFA-Startzustände (oft nur einer).

2. Für jedes Symbol: Berechne alle möglichen Folgezustände (ε-Übergänge berücksichtigen).

3. Neue Zustände: Jeder neue Zustand im DFA entspricht einer neuen Kombination von NFA-Zuständen.

4. Endzustände: Jeder DFA-Zustand, der einen Endzustand des NFA enthält, wird ein Endzustand.

---

3. Beispiel zur Potenzmengenkonstruktion

---

4. Anwendungsgebiete der Potenzmengenkonstruktion

• Compilerbau: Optimierung von regulären Ausdrücken.

• Spracherkennung: Verarbeitung komplexer regulärer Sprachen.

• Theoretische Informatik: Nachweis der Äquivalenz von NFA und DFA.