Aus ProgrammingWiki

Tm-Codierung

Aufgabe

Es soll anhand einer gegebenen

• kontextfreien Grammatik
• Kodierung für Turingmaschinen

ein Compiler entwickelt werden, der eine korrekte TM-Codierung nimmt, und diese in eine Turing-Maschine in der AtoCC-Repräsentation übersetzt. Diese Repräsentation ist eine XML-Datei, welche in dem Tool AutoEdit aus AtoCC geöffnet werden kann.

Die Grammatik :

N = {TMcodierung, 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 -> 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
}
s = TMcodierung

Die Kodierung von Turing-Maschinen ist ebenfalls gegeben:

Lösung

Der darauf entwickelte Compiler kann im CompilerWiki getestet werden.