utm

Aus ProgrammingWiki

Archivierte Version vom 2015-06-13T11:17:00+00:00. Aktuelle Version

Universelle Turingmaschine

(1) 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)

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

(2) Als Beispiel betrachten wir die Turingmaschine

$M = (\{q_{0},q_{1},q_{2}\},\{\text{0},\text{1}\},\{\$,\text{0},\text{1}\},\delta,q_{0},\$,\{q_{0},q_{1}\})$

Verwenden Sie AutoEdit (aus AtoCC) und simulieren Sie die Anwendung von M auf diverse Eingabewörter. Darunter sollte es Wörter w geben, für die M(w)

in einem Endzustand stoppt (\epsilon, 0, 1, 0101010110),
in einem Nicht-Endzustand stoppt (11, 111, 1111),
nicht stoppt (10).

Schauen Sie sich auch den Übergangsgraph von M an.

(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
\vdots	\vdots
q_n	1^{n+1}
L	1
R	11
N	111

utm

Universelle Turingmaschine

Suche