Grammatik

TMcodierung -> Delta Trenner Endzustaende
Trenner -> 0 0
Endzustaende -> Zustand 0 Endzustaende | Zustand
Delta -> Uebergang 0 Delta | Uebergang
Uebergang -> Zustand 0 Zeichen 0 Zustand 0 Zeichen 0 Kopfbewegung
Kopfbewegung -> N | R | L
L -> 1
R -> 1 1
N -> 1 1 1
Zeichen -> B | Eins | Null
Null -> 1
Eins -> 1 1
B -> 1 1 1
Zustand -> Einsenfolge
Einsenfolge -> 1 | 1 Einsenfolge

Beispiel-Maschine

Definition

$ M = (\{q_0, q_1, q_2\}, \{0, 1\}, \{\$, 0, 1\}, \$, q_0, \$, \{q_0, q_1\}) $

Übergangsgraph

Kodierte Beispiel-Maschine

Anhand der vorgegebenen Kodierungvorschrift ergibt sich folgendes Wort für die Turing-Maschine:

101101101101101101010101011011011101101101110110101101001011