utm

Aus ProgrammingWiki

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

{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

Zusätzlich müssen die Endzustände definiert werden.

q0, q1
1 0 11

Daraus ergibt sich die folgende Kodierung \langle M \rangle :

1 0 11 0 11 0 11 0 11 0 11 0 1 0 1 0 1 0 1 0 11 0 11 0 111 0 11 0 11 0 111 0 11 0 1 0 11 0 1 00 1 0 11

(4) 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.

(a) Die reduzierte Grammatik ohne die Regel Trenner -> 0 0 da es sonst zu shift-reduce-Konflikten kommen kann.

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

(b) Struktur des Zieldokuments mit weggelassenen Layout-Eigenschaften

<?xml version="1.0" encoding="utf-8"?>
<AUTOMATON>
	<TYPE value="TM"/>
	<ALPHABET>
		<ITEM value="0"/>
		<ITEM value="1"/>
	</ALPHABET>
	<TAPEALPHABET>
		<ITEM value="$"/>
		<ITEM value="0"/>
		<ITEM value="1"/>
	</TAPEALPHABET>
	<STATE name="q_0" finalstate="true">
		<TRANSITION target="q_1">
			<LABEL read="1" direction="RIGHT" write="1" />
		</TRANSITION>
	</STATE>
	<STATE name="q_1" finalstate="true">
		<TRANSITION target="q_0">
			<LABEL read="0" direction="LEFT" write="0" />
		</TRANSITION>
		<TRANSITION target="q_2">
			<LABEL read="1" direction="RIGHT" write="1" />
		</TRANSITION>
	</STATE>
	<STATE name="q_2" finalstate="false">
		<TRANSITION target="q_0">
			<LABEL read="1" direction="LEFT" write="1" />
		</TRANSITION>
	</STATE>
	<INITIALSTATE value="q_0" />
	<TAPEINITIALCHAR value="$" />
</AUTOMATON>

utm

Universelle Turingmaschine

Suche