Rechnungen und Sprachen von Automaten

Für (p, c, q) $\in$ T(A) schreiben wir auch p$\;\stackrel{{c}}{{\to}}\;$_Aq.

Für ein Wort w = c₁c₂...c_n und Zustände p₀, p₁,..., p_n mit

p₀$$\;\stackrel{{c_1}}{{\to}}\;$$_Ap₁$$\;\stackrel{{c_2}}{{\to}}\;$$_A...$$\;\stackrel{{c_n}}{{\to}}\;$$_Ap_n

schreiben wir p₀$\;\stackrel{{w}}{{\to}}\;$_Ap_n.

(es gibt in A einen mit w beschrifteten Pfad von p₀ nach p_n).

Die von A akzeptierte Sprache ist

L(A) = {w | $$\exists$$p₀ $$\in$$ S, p_n $$\in$$ F : p₀$$\;\stackrel{{w}}{{\to}}\;$$_Ap_n}

(die Menge aller Wörter w, für die es in A einen akzeptierenden Pfad von einem Start- zu einem akzeptierenden Zustand gibt)