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$ 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.
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 diser 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 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:
<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 für 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.
= 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