Unterschied zwischen NEA und DEA endliche Automaten?

Ein Nichtdeterministischer Endlicher Automat (NEA) und ein Deterministischer Endlicher Automat (DEA) sind zwei Arten von endlichen Automaten, die sich in ihrer Funktionsweise unterscheiden:

1. **Deterministischer Endlicher Automat (DEA)**:
- **Zustandsübergänge**: Für jeden Zustand und jedes Eingabesymbol gibt es höchstens einen Folgezustand.
- **Eindeutigkeit**: Der Automat hat zu jedem Zeitpunkt genau einen möglichen Zustand, in den er übergehen kann.
- **Formal**: Ein DEA ist ein 5-Tupel (Q, Σ, δ, q0, F), wobei:
- Q: Endliche Menge von Zuständen
- Σ: Eingabealphabet
- δ: Übergangsfunktion (Q × Σ → Q)
- q0: Anfangszustand (q0 ∈ Q)
- F: Menge der Endzustände (F ⊆ Q)

2. **Nichtdeterministischer Endlicher Automat (NEA)**:
- **Zustandsübergänge**: Für jeden Zustand und jedes Eingabesymbol kann es mehrere mögliche Folgezustände geben.
- **Mehrdeutigkeit**: Der Automat kann sich in mehreren Zuständen gleichzeitig befinden (durch Verzweigungen).
- **Formal**: Ein NEA ist ein 5-Tupel (Q, Σ, δ, q0, F), wobei:
- Q: Endliche Menge von Zuständen
- Σ: Eingabealphabet
- δ: Übergangsfunktion (Q × Σ → P(Q)), wobei P(Q) die Potenzmenge von Q ist (d.h., δ gibt eine Menge von möglichen Folgezuständen zurück)
- q0: Anfangszustand (q0 ∈ Q)
- F: Menge der Endzustände (F ⊆ Q)

**Zusammenfassung**:
- Ein DEA hat für jede Kombination von Zustand und Eingabesymbol genau einen Folgezustand.
- Ein NEA kann für jede Kombination von Zustand und Eingabesymbol mehrere mögliche Folgezustände haben.

Trotz dieser Unterschiede sind beide Automaten äquivalent in dem Sinne, dass jeder NEA in einen äquivalenten DEA umgewandelt werden kann, der dieselbe Sprache akzeptiert.