TM-Codierung (Kretschmer, Schumann)

Aus ProgrammingWiki

back

Inhaltsverzeichnis 1 Aufgabe 1 2 Aufgabe 2 3 Aufgabe 3 4 Aufgabe 4 5 Aufgabe 5

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)

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

$\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:

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:
(Symbol, Kodierung)

(0,1),(1,11),(B,111),($q_0$,1),($q_1$,11),....,($q_n$,$1^{(n+1)}$),(L,1),(R,11),(N,111)

Kodierungsregel:

Übergang → Zustand 0 Zeichen 0 Zustand 0 Zeichen 0 Kopf bewegung

Ü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:

Tom_Ableitung.pdf (0.1 MB)

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:

Tom_Kreativaufgabe_Turingmaschine.zip (0.7 MB)