BuK-KA-UTM

Aus ProgrammingWiki

Archivierte Version vom 2013-05-21T20:05:23+00:00. Aktuelle Version

Inhaltsverzeichnis

1 Deutschmann, Horbach
2 sitosalz

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.

Die Aufgabenstellung dieser Kreativaufgabe ist hier zu finden. Nach Fertigstellung der Aufgabe soll der fertige Compiler im Compilerwiki hochgeladen und verlinkt sein.

Zur Erstellungszeit diser Wiki-Seiten war das Compilerwiki allerdings nicht verfügbar.

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

Als Beispiel soll die Turingmaschine M mit folgender Definition dienen:

$M = (\{q_0, q_1, q_2\}, \{0, 1\}, \{\$, 0, 1\}, \delta, q_0, \$, \{q_0, q_1\})$

Simulation der TM

Die Turingmaschine stoppt für folgende Wörter:

\epsilon
0
1
0101010110

Die Turingmaschine stoppt in einem Nicht-Endzustand für die Wörter:

11
111
1111

Die Turingmaschine stoppt nicht für:

Kodierung der TM

Die Turingmaschine soll nun unter Verwendung der folgenden Kodierungsregeln per Hand kodiert werden:

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

Fasst man nun die einzelnen Kodierungen zusammen ergibt das die folgenden Teilkodierung:

1011011011011 0 1101010101 0 110110111011011 0 1110110101101

Für eine vollständige Kodierung fehlen noch die Endzustände, welche durch den Trenner (00) abgetrennt werden:

Endzustände:
1 0 11

Turingmaschine (gesamt):
1011011011011 0 1101010101 0 110110111011011 0 1110110101101 00 1011

Die Compiler-Zielsprache

Die Zielsprache des Compilers ist die AtoCC-Repräsentation einer Turingmaschine (d.h. ein XML-Dokument für Autoedit). Der Hinweis im Aufgabenblatt ist sehr wichtig. Demnach muss man die Regel \text{Trenner} \to 0 0 streichen und dafür später im Scanner ein Token definieren.

Die reduzierte Grammatik ist dann wie folgt:

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

Nachdem aus dieser Grammatik ein Compiler exportiert wurde, kann man nun im VCC ein Token für 0 0 definieren. Das behebt das Shift-Reduce Problem.

Die XML-Struktur des Zieldokumentes entspricht nach Weglassen von Zusatzinformationen dem folgenden Aufbau:

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

Die entfernten Elemente befinden sich im LAYOUT-Block. Innerhalb dieses Blockes stehen Angaben zum Simulationsinput, zur Darstellung des Übergangsgraphen und zur verwendeten Schriftart. Diese Angaben sind nicht Bestandteil der durch G definierten Sprache und somit werden sie nicht benötigt. AtoCC kann mit dem Fehlen der Angaben umgehen, da es Vorgabewerte verwendet.

Der Compiler

Der Compiler wurde mithilfe von kfg Edit nach VCC exportiert. In VCC folgten die Einstellungen für einen Java-Compiler und LALR(1) für den Parsertyp. Anschließend wurde das Token für die entfernte Trenner-Regel angelegt.

Als Parserdefinition wurde der folgende Code verwendet:

private String xmlHead = "<?xml version=\"1.0\" encoding=\"utf-8\"?>\n<AUTOMATON>\n" 
        + "\t<TYPE value=\"TM\"/>\n\t<ALPHABET>\n\t\t<ITEM value=\"0\"/>\n\t\t<ITEM value=\"1\"/>\n" 
        + "\t</ALPHABET>\n\t<TAPEALPHABET>\n\t\t<ITEM value=\"$\"/>\n\t\t<ITEM value=\"0\"/>\n" 
        + "\t\t<ITEM value=\"1\"/>\n\t</TAPEALPHABET>\n";
private String xmlTail = "\t<TAPEINITIALCHAR value=\"$\" />\n</AUTOMATON>";

ArrayList<ArrayList<String>> transitions = new ArrayList<ArrayList<String>>();
ArrayList<String> stateOccurance = new ArrayList<String>();
ArrayList<String> finalStates = new ArrayList<String>();

private String getInitialState() {
	return "\t<INITIALSTATE value=\"" + stateOccurance.get(0) + "\" />\n";
}

private void addTransition(String startState, String readSign, String targetState, String writeSign, String headMove) {
	int stateIndex;
	stateIndex = stateOccurance.indexOf(startState);
        if (stateIndex < 0) {
		stateOccurance.add(startState);
		stateIndex = stateOccurance.indexOf(startState);
	}
	
	if (stateIndex == transitions.size()) {
		transitions.add(stateIndex, new ArrayList<String>());
	}

	transitions.get(stateIndex).add(getTransitionString(targetState, readSign, headMove, writeSign));
}

private void addFinalStates(String[] split) {
	for (String fin : split) {
		finalStates.add(getStateName(fin));
	}
}

private String getTransitions() {
	String stateTags = "";
	
	for (int i=0; i<stateOccurance.size(); i++) {
		stateTags += "\t<STATE name=\"" + stateOccurance.get(i) + "\" finalstate=\"" + finalStates.contains(stateOccurance.get(i)) + "\">\n";
		
		for (int j=0; j<transitions.get(i).size(); j++) {
			stateTags += transitions.get(i).get(j);
		}
		
		stateTags += "\t</STATE>\n";
	}
	
	return stateTags;
}

private String getTransitionString(String targetState, String readSign, String headMove, String writeSign) {
	String transitionString = "";
	transitionString += "\t\t<TRANSITION target=\"" + targetState + "\">\n";
	transitionString += "\t\t\t<LABEL " + getReadString(readSign) + " "+ getDirectionString(headMove) + " "+ getWriteString(writeSign) + " />\n";
	transitionString += "\t\t</TRANSITION>\n";
	return transitionString;
}

private String getWriteString(String string) {
        return "write=\"" + string + "\"";
}

private String getDirectionString(String string) {
	return "direction=\"" + string + "\"";
}

private String getReadString(String string) {
	return "read=\"" + string + "\"";
}

private String getStateName(String state) {
	return "q_" + (state.length() - 1) + "";
}

Nach der Angabe des globalen Java Codes wurden die Verarbeitungsschritte für die einzelnen Token festgelegt. Diese können in der VCC-Darstellung eingesehen werden.

Die durch den Compiler erzeugte XML-Datei kann in AutoEdit geladen werden. Eine Übereinstimmung mit der ursprünglichen Turingmaschine M lässt sich sehr einfach in der Darstellung der Übergangstabelle feststellen.

sitosalz

Aufgabenstellung

TM-Codierung: kfG und Compiler in AtoCC-TM-Repräsentation (als Zielsprache)

Anleitung: s. 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

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

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.

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

Sitosalz_UTM.zip

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

BuK-KA-UTM

Inhaltsverzeichnis

Deutschmann, Horbach

Aufgabenstellung

Grammatik der TM-Codierungen

Die Turingmaschine M

Simulation der TM

Kodierung der TM

Die Compiler-Zielsprache

Der Compiler

sitosalz

Aufgabenstellung

Grammatik

Beispiel-Turingmaschine

Simulation der TM

Kodierung

Dateien

Compiler

Suche