BuK-KA-UTM

Aufgabenstellung

TM-Codierung: kfG und Compiler in AtoCC-TM-Repräsentation (als Zielsprache)

• Anleitung: s. Aufgabenblatt
• Compiler im Compilerwiki und von ProgrammingWiki aus verlinken

Grammatik

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)

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

Beispiel-Maschine

Definition

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

Übergangsgraph

Kodierte Beispiel-Maschine

\delta(q_0,1) = (q_0,1,R) \mathrel{\widehat{=}} 1011011011011\text{   0} 
\delta(q_1,0) = (q_0,0,L) \mathrel{\widehat{=}} 1101010101\text{   0} 
\delta(q_1,1) = (q_2,1,R) \mathrel{\widehat{=}} 110110111011011\text{   0} 
\delta(q_2,1) = (q_0,1,L) \mathrel{\widehat{=}} 1110110101101\text{   00   1011} 

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

101101101101101101010101011011011101101101110110101101001011

Compiler

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)

Verwenden Sie VCC, um einen entsprechenden Compiler zu beschreiben und zu erzeugen. Wenden Sie diesen Compiler auf die TM-Kodierung von M an und überprüfen Sie, ob die ursprüngliche Maschine  M (in Auto Edit) entsteht.

http://www.michael-hielscher.de/compilerwiki/index.php/CompilerBuK_TM