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)