BuK/IIm10/BuK-Kreativaufgabe07 G2

Wiki-Quelltext dieser Seite.

= 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 [http://atocc.de/ AtoCC] geöffnet werden kann.

Die Grammatik <math>G=(N,T,P,s)</math>:

 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:

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

== Lösung ==

Der darauf entwickelte Compiler kann im [http://michael-hielscher.de/compilerwiki/index.php?title=Compiler_37903_Demo_2 CompilerWiki] getestet werden.