BuK/IIm11/BuK-KA-UTM
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>XSLT</language>
= 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$ kodiert werden.
Aufbauend auf $G$ soll nun ein Compiler erstellt werden, der die Codierung von $M$ in eine von ATOCC lesbare Form (XML Dokument) kompiliert.
Die Aufgabenstellung dieser Kreativaufgabe ist [http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeitstheorie/KA/thema05.pdf hier] zu finden. Nach Fertigstellung der Aufgabe soll der fertige Compiler im Compilerwiki hochgeladen und verlinkt sein.
Zur Erstellungszeit dieser Wiki-Seiten war das Compilerwiki allerdings nicht verfügbar.
== 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\})$
[[Bild:Fdeutschmann_BeispielTMTransitiontable.gif]]
=== 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:
{| cellpadding="6" cellspacing="0" border="1"
|'''Symbol'''
|'''Kodierung'''
|-
|0
|1
|-
|1
|11
|-
|B
|111
|-
|$q_0$
|1
|-
|$q_1$
|11
|-
|$\vdots$
|$\vdots$
|-
|$q_n$
|$1^{n+1}$
|-
|L
|1
|-
|R
|11
|-
|N
|111
|}
(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 1011
== 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:
<code id="519b0ccb43b57"><?xml version="1.0" encoding="utf-8"?>
<AUTOMATON>
<TYPE value="TM"/>
<ALPHABET>
<ITEM value="0"/>
<ITEM value="1"/>
</ALPHABET>
<TAPEALPHABET>
<ITEM value="$"/>
<ITEM value="0"/>
<ITEM value="1"/>
</TAPEALPHABET>
<STATE name="q_0" finalstate="true">
<TRANSITION target="q_1">
<LABEL read="1" direction="RIGHT" write="1" />
</TRANSITION>
</STATE>
<STATE name="q_1" finalstate="true">
<TRANSITION target="q_0">
<LABEL read="0" direction="LEFT" write="0" />
</TRANSITION>
<TRANSITION target="q_2">
<LABEL read="1" direction="RIGHT" write="1" />
</TRANSITION>
</STATE>
<STATE name="q_2" finalstate="false">
<TRANSITION target="q_0">
<LABEL read="1" direction="LEFT" write="1" />
</TRANSITION>
</STATE>
<INITIALSTATE value="q_0" />
<TAPEINITIALCHAR value="$" />
</AUTOMATON></code>
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.
== Der Compiler ==
Der Compiler wurde mithilfe von kfg Edit nach VCC exportiert. In VCC folgten die Einstellungen für einen Java-Compiler und LALR(1) für den Parsertyp. Anschließend wurde das Token für die entfernte Trenner-Regel angelegt.
Als Parserdefinition wurde der folgende Code verwendet:
<code id="519bd130782b0">
private String xmlHead = "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n<AUTOMATON>\n"
+ "\t<TYPE value=\"TM\"/>\n\t<ALPHABET>\n\t\t<ITEM value=\"0\"/>\n\t\t<ITEM value=\"1\"/>\n"
+ "\t</ALPHABET>\n\t<TAPEALPHABET>\n\t\t<ITEM value=\"$\"/>\n\t\t<ITEM value=\"0\"/>\n"
+ "\t\t<ITEM value=\"1\"/>\n\t</TAPEALPHABET>\n";
private String xmlTail = "\t<TAPEINITIALCHAR value=\"$\" />\n</AUTOMATON>";
ArrayList<ArrayList<String>> transitions = new ArrayList<ArrayList<String>>();
ArrayList<String> stateOccurance = new ArrayList<String>();
ArrayList<String> finalStates = new ArrayList<String>();
private String getInitialState() {
return "\t<INITIALSTATE value=\"" + stateOccurance.get(0) + "\" />\n";
}
private void addTransition(String startState, String readSign, String targetState, String writeSign, String headMove) {
int stateIndex;
stateIndex = stateOccurance.indexOf(startState);
if (stateIndex < 0) {
stateOccurance.add(startState);
stateIndex = stateOccurance.indexOf(startState);
}
if (stateIndex == transitions.size()) {
transitions.add(stateIndex, new ArrayList<String>());
}
transitions.get(stateIndex).add(getTransitionString(targetState, readSign, headMove, writeSign));
}
private void addFinalStates(String[] split) {
for (String fin : split) {
finalStates.add(getStateName(fin));
}
}
private String getTransitions() {
String stateTags = "";
for (int i=0; i<stateOccurance.size(); i++) {
stateTags += "\t<STATE name=\"" + stateOccurance.get(i) + "\" finalstate=\"" + finalStates.contains(stateOccurance.get(i)) + "\">\n";
for (int j=0; j<transitions.get(i).size(); j++) {
stateTags += transitions.get(i).get(j);
}
stateTags += "\t</STATE>\n";
}
return stateTags;
}
private String getTransitionString(String targetState, String readSign, String headMove, String writeSign) {
String transitionString = "";
transitionString += "\t\t<TRANSITION target=\"" + targetState + "\">\n";
transitionString += "\t\t\t<LABEL " + getReadString(readSign) + " "+ getDirectionString(headMove) + " "+ getWriteString(writeSign) + " />\n";
transitionString += "\t\t</TRANSITION>\n";
return transitionString;
}
private String getWriteString(String string) {
return "write=\"" + string + "\"";
}
private String getDirectionString(String string) {
return "direction=\"" + string + "\"";
}
private String getReadString(String string) {
return "read=\"" + string + "\"";
}
private String getStateName(String state) {
return "q_" + (state.length() - 1) + "";
}</code>
Nach der Angabe des globalen Java Codes wurden die Verarbeitungsschritte für die einzelnen Token festgelegt. Diese können in der VCC-Darstellung eingesehen werden.
Die durch den Compiler erzeugte XML-Datei kann in AutoEdit geladen werden. Eine Übereinstimmung mit der ursprünglichen Turingmaschine $M$ lässt sich sehr einfach in der Darstellung der Übergangstabelle feststellen.
== Link zum fertigen TM-Compiler ==
TODO
<!--
= sitosalz =
== Aufgabenstellung ==
TM-Codierung: kfG und Compiler in AtoCC-TM-Repräsentation (als Zielsprache)
* Anleitung: s. [http://www.inf.hs-zigr.de/~wagenkn/TI/Berechenbarkeitstheorie/KA/thema05.pdf 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
{|| border="1" cellpadding="5" cellspacing="0"
!$\delta$
!$\$$
!0
!1
|-
||$q_0$||-||-|| $(q_1,1,R)$
|-
||$q_1$||-||$(q_0,0,L)$||$(q_2,1,R)$
|-
||$q_2$||-||-||$(q_0,1,L)$
|}
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:
[[Bild:Sirorose_Bildschirmfoto_2012-05-03_um_19.32.33.png]]
=== 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.
{| border="1" cellpadding="5" cellspacing="0"
!Symbol
!Kodierung
|-
|| 0 || 1
|-
|| 1 || 11
|-
|| $q_0$ || 1
|-
|| $q_1$ || 11
|-
|| $q_2$ || 111
|-
|| L || 1
|-
|| R || 11
|-
|| N || 111
|-
|}
$\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 ==
<document>Sitosalz_UTM.zip</document>
== 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
-->