BuK-Kreativaufgabe07 G2

Aus ProgrammingWiki
< BuK < IIm10

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 G=(N,T,P,s):

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:

\begin{tabular}[ht]{c|c} Symbol & Kodierung \\ \hline 0 & 1 \\ 1 & 11 \\ \hline B & 111 \\ q0 & 1 \\ q1 & 11 \\ ... & ... \\ qn & 1n+1 \\ \hline L & 1 \\ R & 11 \\ N & 111 \\ \end{tabular}

Lösung


Der darauf entwickelte Compiler kann im CompilerWiki getestet werden.