Automaten

Automat A = (Σ, Q, I, F, δ) mit

• Q Menge der Zustände
• I⊆Q Menge der initialen Zustände
• F⊆Q Menge der finalen Zustände
• Σ Menge der Kantenmarkierungen (Alphabet)
• δ⊆Q×Σ×Q Übergangsrelation

markierter Weg in A: (v₀, c₁, v₁, c₂, v₂,…, v_n-1, c_n, v_n)
so daß ∀0≤i < n : (v_i, c_i+1, v_i+1)∈δ.

Schreibweise: v₀$\;\stackrel{{w}}{{\to}}\;$_Av_n mit w = c₁c₂…c_n

Die Sprache des Automaten: L(A) = {w | ∃i∈I : ∃f∈F : i$\;\stackrel{{w}}{{\to}}\;$_Af}