Berechnung eines GNEA

Einfache Sprache

Def. Berechnung eines GNEA

Sei $\mathcal{A}=(Q,A,\delta,q_I,q_F)$ ein GNEA. Dann ist eine Folge $q_0q_1\ldots q_{n+1}$ mit $q_i\in Q,\: 0\leq iBerechnung von $\mathcal{A}$ auf $u\in A^*$ falls gilt:

• $u$ lässt sich als Konkatenation von Teilwörtern $u_0u_1\ldots u_n$ mit $\forall i\in [0,n]:u_i\in A^*$ schreiben,
• $q_0 = q_I$,
• $\forall i \in [1,n-1]: q_i\not\in\{q_I,q_F\}$ und
• $\forall i \in [0,n]: u_i\in L(\delta(q_i,q_{i+1}))$

Bemerke: Eine Berechnung heißt akzeptiert, falls $q_n=q_F$.