Java - Universelle Turingmaschine

From XennisWiki
Jump to: navigation, search

Beispiele für w

L(UTM) = {ww(rev)}

00000001000101000000010100010000000100010001010100100010010100100000100010010010001000010001010010100101001001001001001001000010100010001010001000101000100100010100010101000100100010010100000100010000001000101000001010000010100100000100100000100100100000010010001000101

L(UTM) = {w | w = {0}*}

001000101001010001001000100010101010001001

UTM.java

import java.util.ArrayList;
import java.util.List;

/**
 * Universelle Turingmaschine
 *
 * Version 1.1
 */
public class UTM {

	/**
	 * Main Methode
	 *
	 * @param args w#x mit w binäre Kodierung einer TM und x binäre Eingabe
	 */
	public static void main(String[] args)
	{
		try {
			// Eingabe in w und x zerlegen
			String[] eingabe = args[0].split("#");
			String w = eingabe[0];
			String x = ""; // Entspricht: Lambda
			if(eingabe.length > 1) {
				x = eingabe[1];
			}
			// Turing-Maschine M_w
			TM Mw = konvertiereKodierungZuTm(w);
			//System.out.println(Mw);
			// Berechnung und Ausgabe
			if( Mw.berechnung(x) ) {
				System.out.println("1");
			} else {
				System.out.println("0");
			}
		} catch (Exception e) {
			System.out.println(e);
		}
	}

	/**
	 * Dekodiert die binäre Kodierung einer Turing-Maschine und gibt die
	 * entsprechende Turing-Maschine zurück
	 *
	 * Kodierung
	 * anzahlZustaende 1 anzahlBandalphabet 1 anzahlAkzeptierteZustaende 1 [akzeptierteZustaende] [Transitionen]
	 * 
	 * @param w	Kodierung einer Turing-Maschine
	 * @return Turing-Maschine
	 * @throws Exception
	 */
	private static TM konvertiereKodierungZuTm(String w) throws Exception
	{
		List<String> list = zerlegeKodierung(w);
		
		List<Integer> akzeptierteZustaende = new ArrayList<Integer>();
		Konfiguration[][] uebergangsfunktion;
		
		/*
		 * Kardinalität (1) der Zustände, (2) des Bandalphabets und (3) der
		 * akzeptieren Zustände dekodieren
		 */
		int anzahlZustaende = list.get(0).length();
		int anzahlBandalphabet = list.get(1).length();
		int anzahlAkzeptierteZustaende = list.get(2).length();
		/*
		 * Die akzeptierten Zustände dekodieren
		 */
		for(int i=0; i<anzahlAkzeptierteZustaende; i++) {
			int zustandNummer = list.get(3+i).length();
			akzeptierteZustaende.add( zustandNummer );
		}
		/*
		 * Transitionen dekodieren
		 * 
		 * Sigma(q, a) = (p, b, e)
		 * Kodierung: 0^q10^b10^p10^b10^e1
		 * 
		 * 		- q: Zustand Element Q
		 * 		- a: Symbol Element Gamma
		 * 		- p: Zustand Element Q
		 * 		- b: Symbol Element Gamma
		 * 		- e: Kopfbewegung Element {l, r, 0}
		 */
		uebergangsfunktion = new Konfiguration[anzahlZustaende][anzahlBandalphabet];
		for(int i=3 + anzahlAkzeptierteZustaende; i<list.size(); i++) {
			int q = list.get(i).length();	// Dekodiert
			String a = list.get(++i);		// Kodiert
			int p = list.get(++i).length(); // Dekodiert
			String b = list.get(++i);		// Kodiert
			String k = list.get(++i);		// Kodiert
			
			uebergangsfunktion[ q-1 ][ a.length()-1 ] = new Konfiguration(p, b, k);
		}
	
		return new TM(anzahlZustaende, anzahlBandalphabet, akzeptierteZustaende, uebergangsfunktion);
	}

	/**
	 * Zerlegt die Kodierung einer Turing-Maschine
	 * 
	 * @param s Kodierung einer Turing-Maschine
	 * @return list Zerlegte Kodierung
	 * @throws Exception
	 */
	private static List<String> zerlegeKodierung(String w) throws Exception
	{
		List<String> list = new ArrayList<String>();
		String temp = "";
		
		for(int i=0; i<w.length(); i++) {
			if(w.charAt(i) == '1') {
				list.add( temp );
				temp = "";
			} else {
				temp += w.charAt(i);
			}
		}
		
		return list;
	}
}

TM.java

import java.util.ArrayList;
import java.util.List;


public class TM {

	private int anzahlZustaende;
	private int anzahlBandalphabet;
	private List<Integer> akzeptierteZustaende;
	private Konfiguration[][] uebergangsfunktion;
	private List<Character> x = new ArrayList<Character>();
	/*
	 * (1) Zustand, indem sich die TM aktuell befindet (q1 ist immer
	 *     Startzustand)
	 * (2) Aktuelle Position des Lese- und Schreibkopfs der TM
	 */
	private int zustand = 1;
	private int position = 0;
	
	/**
	 * Konstruiere eine Turing-Maschine 
	 * 
	 * M = (Q, Sigma, Gamma, Delta, q1, F)
	 * 
	 *		- Sigma = Gamma\{Blanksymbol}
	 * 
	 * @param anzahlZustaende ( |Q| )
	 * @param anzahlBandalphabet ( |Gamma| )
	 * @param akzeptierteZustaende Dekodierte, akzeptierte Zustände ( F )
	 * @param uebergangsfunktion ( Delta )
	 */
	public TM(int anzahlZustaende, int anzahlBandalphabet, List<Integer> akzeptierteZustaende, Konfiguration[][] uebergangsfunktion)
	{
		this.anzahlZustaende = anzahlZustaende;
		this.anzahlBandalphabet = anzahlBandalphabet;
		this.akzeptierteZustaende = akzeptierteZustaende;
		this.uebergangsfunktion = uebergangsfunktion;
	}
	
	/**
	 * Turing-Maschine führt die Berechnung für die Eingabe x durch
	 * 
	 * @param x binärer Eingabestring
	 * @return boolean Erfolgreiche Berechnung
	 */
	public Boolean berechnung(String x)
	{	
		// Eingabe x einlesen
		for(int i=0; i<x.length(); i++) {
			this.x.add(x.charAt(i));
		}

		try {
			while( !this.akzeptierteZustaende.contains(this.zustand) ) {
				
				/*
				 * Befindet sich der Lese- und Schreibkopf vor oder hinter dem
				 * Eingabewort x, füge dort das Blanksymbol hinzu, da das Band
				 * nicht von vornherein mit diesen belegt ist.
				 */
				if(this.position<0 || this.position>=this.x.size()) {
					schreibeSymbolAufBand('_');
				}
				// Neue Konfiguration
				Konfiguration konfiguration = this.uebergangsfunktion[this.zustand-1][konvertiereSymbolZuKodierterLaenge( this.x.get(this.position) )-1];
				// Berechnung ausgeben
				//System.out.println("Delta(" + this.zustand + ", " + this.x.get(this.position) + ") = " + konfiguration + "; Band:" + this.x.toString());

				// Ist der aktuelle Zustand nicht definiert, halte an
				if(konfiguration == null) return false;
				
				schreibeSymbolAufBand(konfiguration.getSymbol());

				this.zustand = konfiguration.getZustand();				
				this.position += konfiguration.getWertKopfbewegung();
			}
			return true;
		} catch (Exception e) {
			return false;
		}
	}

	/**
	 * Gibt die Länge der Kodierung des übergebenen Symbols zurück.
	 * 
	 * @param s Gelesenes Symbol
	 * @return Länge der Kodierung des Symbols
	 */
	private int konvertiereSymbolZuKodierterLaenge(Character s) {
		if(s=='0') {
			return 1;	// Kodierung: 0
		} else if(s=='1') {
			return 2;	// Kodierung: 00
		} else {
			return 3;	// Kodierung: 000 (Blanksymbol)
		}
	}
	
	/**
	 * Schreibt das Symbol s auf das Band
	 * 
	 * @param s Symbol
	 * @throws Exception
	 */
	private void schreibeSymbolAufBand(char s) throws Exception
	{
		// Symbol am Anfang einfügen, d.h. vor dem ersten Element
		if(this.position<0) {
			List<Character> tempX = this.x;
			this.x.clear();
			this.x.add(s);
			this.x.addAll(tempX);
			this.position = 0;
		} 
		// Symbol am Ende anfügen
		else if(this.position>=this.x.size()) {
			this.x.add(s);
		}
		// Symbol ersetzen
		else {				
			this.x.set(this.position, s);
		}
	}
	
	/**
	 * Turing-Maschine als String ausgeben
	 */
	public String toString()
	{
		return "M = (Q, Sigma, Gamma, Delta, q1, F)"
				+ "\n    |Q| =" + this.anzahlZustaende
				+ "\n    |Gamma| =" + this.anzahlBandalphabet
				+ "\n    F =" + java.util.Arrays.toString( this.akzeptierteZustaende.toArray() )
				+ "\n    Delta [Zustände][Symbole]:"
				+ "\n    " + java.util.Arrays.deepToString(this.uebergangsfunktion)
				+ "\n";
	}
}

Konfiguration

public class Konfiguration {

	private int zustand;
	private Character symbol;
	private Character kopfbewegung;

	/**
	 * Konstruiere eine Konfiguration
	 * 
	 * k = (q, alpha, beta)
	 * 
	 * 		- q Element Zustände
	 * 		- alpha Element Bandalphabet
	 * 		- beta Element {l, r, 0}
	 * 
	 * @param zustand Dekodierter Zustand
	 * @param symbol Kodiertes Symbol
	 * @param kopfbewegung Kodierte Kopfbewegung
	 */
	public Konfiguration(int zustand, String symbol, String kopfbewegung)
	{
		this.zustand		= zustand;
		this.symbol		= dekodiereSymbol(symbol);
		this.kopfbewegung	= dekodiereKopfbewegung(kopfbewegung);
	}
	
	/**
	 * Gibt den Zustand zurück
	 * 
	 * @return Dekodierter Zustand
	 */
	public Integer getZustand()
	{
		return this.zustand;
	}

	/**
	 * Gibt das Symbol zurück
	 * 
	 * @return Dekodiertes Symbol
	 */
	public Character getSymbol()
	{
		return this.symbol;
	}

	/**
	 * Gibt den Wert der Kopfbewegung zurück
	 * 
	 * @return Wert der Kopfbewegung
	 */
	public Integer getWertKopfbewegung()
	{
		if(this.kopfbewegung == 'l') {
			return -1;
		} else if(this.kopfbewegung == 'r') {
			return +1;
		} else {
			return 0;	
		}
	}

	/**
	 * Gibt die dekodierte Kopfbewegung zurück
	 * 
	 * @param s Kodierte Kopfbewegung
	 * @return Dekodierte Kopfbewegung
	 */
	private Character dekodiereKopfbewegung(String s)
	{
		if(s.length() == 1) {		// Kodierung: 0
			return 'l';
		} else if(s.length() == 2) {	// Kodierung; 00
			return 'r';
		} else {			// Kodierung: 000
			return '0';	
		}
	}

	/**
	 * Gibt das dekodierte Symbol zurück
	 * 
	 * @param s Kodierte Symbol
	 * @return Dekodiertes Symbol
	 */
	private char dekodiereSymbol(String s)
	{
		if(s.length() == 1) {		// Kodierung: 0
			return '0';
		} else if(s.length() == 2) {	// Kodierung: 00
			return '1';
		} else {
			return '_';		// Kodierung: 000 (Blanksymbol)
		}
	}
	
	/**
	 * Gibt die Konfiguration als String aus
	 */
	public String toString()
	{
		return "(" + this.getZustand() + ", " + this.getSymbol() + ", " + this.kopfbewegung + ")";
	}
}