Skip to content

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¶

NFAtoDFA.svg

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.