Zurück

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: