Konfiguration einer TM

Einfache Sprache

Def. Konfiguration einer TM

Eine Konfiguration einer TM $\mathcal{M}=(Q,A,\Gamma,\delta,q_0,\textvisiblespace,q_{acc},q_{rej})$ ist von der Form $(u,q,v)\in(\Gamma^*\times Q\times\Gamma^+)$ wobei $(u,q,v)$ als $uqv$ abgekürzt wird.

Anfangskonfiguration

$q_0w\textvisiblespace$ 

für eine Eingabe $w\in A^*$

Haltekonfiguration

$uq_{acc}v\;\text{oder}\; uq_{rej}v$

für $u\in\Gamma^*,\;v\in\Gamma^+$

Folgekonfiguration

Die Folgekonfiguration von $uqav$ mit $u,v\in\Gamma^*,\;a,c,b\in\Gamma,\;q,q'\in Q$

• $ubq'v$ falls $q,a\longrightarrow q',b,R$ und $v\neq\varepsilon$
• $ubq'\textvisiblespace$ falls $q,a\longrightarrow q',b,R$ und $v=\varepsilon$
• $u'q'cbv$ falls $q,a\longrightarrow q',b,L$ und $u=u'c$
• $q'bv$ falls $q,a\longrightarrow q',b,L$ und $u=\varepsilon$
• $uq'bv$ falls $q,a\longrightarrow q',b,N$