Deutschmann, Horbach

Aufgabenstellung

Mithilfe von kfg Edit aus ATOCC soll zuerst die Sprache der TM-Codierungen durch die Grammatik G definiert werden.

Anschließend soll eine Turingmaschine M in Autoedit beschrieben und die Anwendung von M auf verschiedene Eingabewörter simuliert werden.

Die TM M soll danach mit G codiert werden.

Aufbauend auf G soll nun ein Compiler erstellt werden, der die Codierung von M in eine von ATOCC lesbare Form (XML Dokument) kompiliert.

Grammatik der TM-Codierungen

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

Die Turingmaschine M

Als Beispiel soll die Turingmaschine M mit folgender Definition dienen:

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

Simulation der TM

Die Turingmaschine stoppt für folgende Wörter: \epsilon, 0, 1, 0101010110

Die Turingmaschine stoppt in einem Nicht-Endzustand für die Wörter: 11,111,1111

Die Turingmaschine stoppt nicht für: 10

Kodierung der TM

Die Turingmaschine soll nun unter Verwendung der folgenden Kodierungsregeln per Hand kodiert werden:

(q0,1) = (q1,1,R)
1 0 11 0 11 0 11 0 11

(q1,0) = (q0,0,L)
11 0 1 0 1 0 1 0 1

(q1,1) = (q2,1,R)
11 0 11 0 111 0 11 0 11

(q2,1) = (q0,1,L)
111 0 11 0 1 0 11 0 1

Fasst man nun die einzelnen Kodierungen zusammen ergibt das die folgenden Teilkodierung:

1011011011011 0 1101010101 0 110110111011011 0 1110110101101

Für eine vollständige Kodierung fehlen noch die Endzustände, welche durch den Trenner (00) abgetrennt werden:

Endzustände:
1 0 11

Turingmaschine (gesamt):
1011011011011 0 1101010101 0 110110111011011 0 1110110101101 00 1 0 11

Die Compiler-Zielsprache

Die Zielsprache des Compilers ist die AtoCC-Repräsentation einer Turingmaschine (d.h. ein XML-Dokument für Autoedit). Der Hinweis im Aufgabenblatt ist sehr wichtig. Demnach muss man die Regel \text{Trenner} \to 0 0 streichen und dafür später im Scanner ein Token definieren.

Die reduzierte Grammatik ist dann wie folgt:

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 
   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

Nachdem aus dieser Grammatik ein Compiler exportiert wurde, kann man nun im VCC ein Token für 0 0 definieren. Das behebt das Shift-Reduce Problem.

Die XML-Struktur des Zieldokumentes entspricht nach Weglassen von Zusatzinformationen dem folgenden Aufbau:

Die entfernten Elemente befinden sich im LAYOUT-Block. Innerhalb dieses Blockes stehen Angaben zum Simulationsinput, zur Darstellung des Übergangsgraphen und zur verwendeten Schriftart. Diese Angaben sind nicht Bestandteil der durch G definierten Sprache und somit werden sie nicht benötigt. AtoCC kann mit dem Fehlen der Angaben umgehen, da es Vorgabewerte verwendet.

sitosalz

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 für 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-Turingmaschine

Als Beispiel wird eine Turingmaschine $ M = (\{q_0, q_1, q_2\}, \{0, 1\}, \{\$, 0, 1\}, \$, q_0, \$, \{q_0, q_1\}) $ mit folgender Übergangstabelle

betrachtet. Die Übergangstabelle wird in AutoEdit (aus AtoCC) überführt und als Automatentyp TM ausgewählt.

Anschließend wird folgender Übergangsgraph für die Beispiel-Turingmaschine in AtoCC angezeigt:

Simulation der TM

Im nächsten Schritt werden Wörter w für die TM simuliert.

Kodierung

In der folgenden Tabelle sind die Kodierungen, welche sich aus der Grammatik G ergeben, für die Beispiel-Turingmaschine ersichtlich.

\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} 

Endzustände:    1011

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

101101101101101101010101011011011101101101110110101101001011

Dateien

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