BuK/IIm11/BuK-KA-UTM

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 ==

= 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