Berechnung eines NEA

Einfache Sprache

Def. Berechnung eines NEA

Sei $\mathcal{A}=(Q,A,\delta,I,F)$ ein NEA. Dann ist eine Folge $r_0r_1\ldots r_n$ mit $r_i\in Q,\: 0\leq iBerechnung von $\mathcal{A}$ auf $w\in A^*$ falls gilt:

• $w$ lässt sich schreiben als $x_0x_1\ldots x_{m-1}$ mit $x\in A_\epsilon, (m\geq |w|)$
• $r_0\in I$
• $q_{i+1}\in\hat\delta(q_i,x_i)$ f. a. $0\leq i

Bemerke: Eine Berechnung heißt akzeptiert, falls $q_m\in F$.

w-Pfad