Berechnung

Def. Berechnung DEA

Sei $\mathcal A=(Q,A,\delta,q_I,F)$ ein DEA und $x=x_0\ldots x_{n-1}\in A^+$ mit $x_i\in A$ und $0\leq iBerechnung von $\mathcal A$ auf $x$ eine Folge $r_0r_1\ldots r_n$ mit $r_i\in Q,\: 0\leq i

1. $r_0=q_I$,
2. $\delta(r_i,x_i)=r_{i+1}$ f. a. $0\leq i \leq n$.

Bemerke: $\mathcal A$ akzeptiert $x$ falls $r_n\in F$.

Def. Berechnung 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$.

Def. Berechnung TM

Sei $\mathcal{M}=(Q,A,\Gamma,\delta,q_0,\textvisiblespace,q_{acc},q_{rej})$ TM. Eine Berechnung von $\mathcal{M}$ auf $w\in A^*$ eine Folge $\kappa_0\kappa_1\ldots$ mit $\kappa_i\in\Gamma^*\times Q\times\Gamma^+$ von Konfiguration. Weiter müssen folgende Eigenschaften gelten:

1. $\kappa_0=q_0w\textvisiblespace$ ist Anfangskonfiguration,
2. für alle $i\in\mathbb{N}$ gilt $\kappa_{i+1}$ ist Folgekonfiguration von $\kappa_i$ und
3. falls Berechnung endlich ist, besitzt die letzte Konfiguration keine Folgekonfiguration

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

• Akzeptierende Berechnung: Berechnung endet in Konfiguration $q_{acc}$
• Verwerfende Berechnung: Berechnung endet in Konfiguration $q_{reg}$
• Divergente Berechnung: Unendliche Folge