TM-Codierung (Kretschmer, Schumann)

Wiki-Quelltext dieser Seite.

[http://programmingwiki.de/BuK/IIm15 back]

== Aufgabe 1 ==
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)<br>

 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

== Aufgabe 2 ==
Als Beispiel betrachten wir die Turingmaschine
$ M = (\{q_0 , q_1 , q_2 \}, \{0, 1\}, \{\$, 0, 1\}, δ, q_0 , \$, \{q_0 , q_1 \})$ mit
{| 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)$
|-
|}

* Eingaben:
{| border="1" cellpadding="5" cellspacing="0"
|+ 
! Eingabewort || Stoppt || Endzustand
|-
|$\epsilon $ || true || true
|-
| 0 || true || true
|-
| 1 || true || true
|-
|0101010110 || true || true
|-
|11 || true|| false
|-
|111 || true || false
|-
|1111 || true || false
|-
|10 || false || -
|-
|}

== Aufgabe 3 ==

Kodieren Sie M aus dem Beispiel per Hand, indem Sie die folgenden Kodierungsregeln
befolgen:<br>
(Symbol, Kodierung)<br>
 (0,1),(1,11),(B,111),($q_0$,1),($q_1$,11),....,($q_n$,$1^{(n+1)}$),(L,1),(R,11),(N,111)
Kodierungsregel:<br>
 Übergang → Zustand 0 Zeichen 0 Zustand 0 Zeichen 0 Kopf bewegung<br>
{| border="1" cellpadding="5" cellspacing="0"
|+ 
! Übergang || Kodiert
|-
|$ (q_0,1) = (q_1 ,1,R) $ || 1 0 11 0 11 0 11 0 11
|-
|$ (q_1,0) = (q_0 ,0,L) $ || 11 0 1 0 1 0 1 0 1
|-
| $ (q_1,1) = (q_2 ,1,R) $ || 11 0 11 0 111 0 11 0 11
|-
| $ (q_2,1) = (q_0 ,1,L) $ || 111 0 11 0 1 0 11 0 1
|-
| ||
|}

Vollständige kodierte Maschine:
 Übergänge                                                    Trenner Endzustände 
 1011011011011 0 1101010101 0 110110111011011 0 1110110101101 00 1011

== Aufgabe 4 ==
Analysieren Sie anschließend das von Ihnen bestimmte Wort $w = encode(M ), w ∈
{0, 1}^+$ . Da G eine kfG ist, gelingt diese Prüfung in jedem Fall. Verfälschen Sie w ein
wenig und parsen Sie das so entstandene Wort.
Ableitung:<br><document>Tom_Ableitung.pdf</document><br>[[Bild:Tom_Beispielkodierung.jpg]]

== Aufgabe 5 ==
Als nächstes soll ein Compiler entwickelt werden, der ein syntaktisch korrektes Wort
aus L(G), also eine korrekte TM-Codierung, in eine TM in der AtoCC-Repräsentation
übersetzt. Beginnen Sie mit der Generierung eines LALR(1)-Parsers für G. Wichtiger
Hinweis: Um shift-reduce-Konflikte zu vermeiden, reduzieren Sie die o.g. Grammatik G,
indem Sie die Regel $Trenner -> 0 0$ streichen und ein entsprechendes Token für den
Scanner definieren.

 Token : Trenner, Expression : 00


Zusammenfassung aller Dateien:<document>Tom_Kreativaufgabe_Turingmaschine.zip</document>