Turingmaschinen zu Grammatik

siehe:
Entscheidbarkeit von Grammatiken
Die Chomsky-Hierarchy

Beweis Turing Maschine zu Grammatik

Annaheme

Konstruktion der Grammatik

Grammatik zu Turing Maschine Idee

Start

[ w _ _ _

Regeln zur Simulation der Berechnung

$\delta (q,a)=(q^{\prime },b,1)$ ⇒ _ _ q a _ _ = _ _ b q' _ _
$\delta (q,a)=(q^{\prime },b,0)$ ⇒ _ _ q a _ _ = _ _ q' b _ _
$\delta (q,a)=(q^{\prime },b,-1)$ ⇒ _ c q a _ _ = _ q' c b _ _

Aufräumen

Beweis Turing Maschine zu Grammatik