Quintupel eines NEA
Im Folgenden ist ein Automat (=Transitionssystem) A = (Q, Σ, I, Δ, F) eines nichtdeterministischen endlichen Automaten (NEA) gegeben.
Fahre mit der Maus über die fünf Bestandteile (=Quintupel) Q, Σ, I, Δ, F des Transitionssystems und erkunde Schritt für Schritt die Definition eines nichtdeterministischen endlichen Automaten!
A = ( Q , Σ , I , Δ , F )
Menge aller Zustände
Q = {q0, q1, q2}
- Die Anzahl der in Q enthaltenen Zustände ist endlich: |Q| < ∞
- Die Darstellung eines Zustands erfolgt mit einem Kreis, der die Bezeichnung des Zustands beinhaltet.
Alphabet (Menge aller Buchstaben)
Σ = {a, b}
- Die Anzahl der im Alphabet enthaltenen Buchstaben ist endlich: |Σ| < ∞
Menge aller Anfangszustände
I = {q0}
- Es gibt genau einen Anfangszustand: |I| = 1
- Ein Anfangszustand besitzt keinen Vorgänger.
- Die Menge der Anfangszustände ist eine Teilmenge aller Zustände: I ⊆ Q
Übergangsrelation (Menge von Übergängen)
Δ = {(q0, a, q1), (q1, b, q2), (q2, a, q2), (q2, b, q2)}
- Übergänge werden auch als Transitionen bezeichnet
- Übergänge haben die Form (Zustand, Buchstabe, Zustand): Q × Σ × Q
- Die Übergangsrelation ist eine Teilmenge aller möglichen Übergänge:
Δ ⊆ Q × Σ × Q
Menge aller Endzustände
F = {q2}
- Die Menge der Endzustände ist eine Teilmenge aller Zustände: F ⊆ Q
- Ein Endzustand ist durch einen Doppelkreis gekennzeichnet, der den Namen des Zustands beinhaltet.
Quintupel eines NEA
Für jeden NEA gilt:
- Für einen Übergang kann es mehrere gleichwertige Möglichkeiten geben.
- Dem Automaten ist nicht vorgegeben, welchen Übergang er zu wählen hat.