BuK/IIm11/BuK-KA-UTM
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
= 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.
== 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
Nach dem 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.
= 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