TM-Codierung (Kretschmer, Schumann)

back

Aufgabe 1

Verwenden Sie kfG Edit aus AtoCC, um die folgende kontextfreie Grammatik G fur die ¨ Sprache der TM-Codierungen zu definieren. G = (N, T, P, s)

N = {TMcodierung, Trenner,
    Endzustaende, Delta, 
    Uebergang, Kopfbewegung, 
    L, R, N, Zeichen, Null,
     Eins, B, Zustand, Einsenfolge}
T = {0, 1}
P = {
   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 -> L | R | N 
   L            -> 1 
   R            -> 1 1 
   N            -> 1 1 1 
   Zeichen      -> Null | Eins | B 
   Null         -> 1 
   Eins         -> 1 1 
   B            -> 1 1 1 
   Zustand      -> Einsenfolge 
   Einsenfolge  -> 1 | 1 Einsenfolge 
}
s = TMcodierung

Aufgabe 2

Als Beispiel betrachten wir die Turingmaschine M = ({q_0 , q_1 , q_2 }, {0, 1}, {, 0, 1}, δ, q_0 , , {q_0 , q_1 }) mit