Skip to content

Instantly share code, notes, and snippets.

@NikolasTzimoulis
Created May 31, 2012 20:44
Show Gist options
  • Save NikolasTzimoulis/2846116 to your computer and use it in GitHub Desktop.
Save NikolasTzimoulis/2846116 to your computer and use it in GitHub Desktop.
A simple implementation of a Turing Machine in Java (which I wrote the night before a Theory of Computation exam instead of studying)
package tm;
public final class MachinesLibrary
{
private MachinesLibrary() {}
public static TuringMachine EqualBinaryWords()
{
TuringMachine newTM = new TuringMachine();
newTM.addState("q1");
newTM.addState("q2");
newTM.addState("q3");
newTM.addState("q4");
newTM.addState("q5");
newTM.addState("q6");
newTM.addState("q7");
newTM.addState("q8");
newTM.addState("qa");
newTM.addState("qr");
newTM.setStartState("q1");
newTM.setAcceptState("qa");
newTM.setRejectState("qr");
newTM.addTransition("q1", '1', "q3", 'x', true);
newTM.addTransition("q1", '0', "q2", 'x', true);
newTM.addTransition("q1", '#', "q8", '#', true);
newTM.addTransition("q2", '0', "q2", '0', true);
newTM.addTransition("q2", '1', "q2", '1', true);
newTM.addTransition("q2", '#', "q4", '#', true);
newTM.addTransition("q3", '0', "q3", '0', true);
newTM.addTransition("q3", '1', "q3", '1', true);
newTM.addTransition("q3", '#', "q5", '#', true);
newTM.addTransition("q4", 'x', "q4", 'x', true);
newTM.addTransition("q4", '0', "q6", 'x', false);
newTM.addTransition("q5", 'x', "q5", 'x', true);
newTM.addTransition("q5", '1', "q6", 'x', false);
newTM.addTransition("q6", '0', "q6", '0', false);
newTM.addTransition("q6", '1', "q6", '1', false);
newTM.addTransition("q6", 'x', "q6", 'x', false);
newTM.addTransition("q6", '#', "q7", '#', false);
newTM.addTransition("q7", '0', "q7", '0', false);
newTM.addTransition("q7", '1', "q7", '1', false);
newTM.addTransition("q7", 'x', "q1", 'x', true);
newTM.addTransition("q8", 'x', "q8", 'x', true);
newTM.addTransition("q8", '_', "qa", '_', true);
return newTM;
}
}
package main;
import tm.*;
public class Main
{
public static void main(String[] args)
{
TuringMachine TM1 = MachinesLibrary.EqualBinaryWords();
boolean done = TM1.Run("010000110101#010000110101", false);
if (done==true)
{
System.out.println("The input was accepted.");
}
else
{
System.out.println("The input was rejected.");
}
}
}
package tm;
import java.util.*;
public class TuringMachine
{
private Set<String> StateSpace;
private Set<Transition> TransitionSpace;
private String StartState;
private String AcceptState;
private String RejectState;
private String Tape;
private String CurrentState;
private int CurrentSymbol;
class Transition
{
String readState;
char readSymbol;
String writeState;
char writeSymbol;
boolean moveDirection; //true is right, false is left
boolean isConflicting(String state, char symbol)
{
if (state.equals(readState) && symbol == readSymbol)
{
return true;
}
else
{
return false;
}
}
}
public TuringMachine()
{
StateSpace = new HashSet<String>();
TransitionSpace = new HashSet<Transition>();
StartState = new String("");
AcceptState = new String("");
RejectState = new String("");
Tape = new String("");
CurrentState = new String("");
CurrentSymbol = 0;
}
public boolean Run(String input, boolean silentmode)
{
CurrentState = StartState;
Tape = input;
while(!CurrentState.equals(AcceptState) && !CurrentState.equals(RejectState))
{
boolean foundTransition = false;
Transition CurrentTransition = null;
if (silentmode == false)
{
if (CurrentSymbol>0)
{
System.out.println(Tape.substring(0, CurrentSymbol) + " " + CurrentState + " " + Tape.substring(CurrentSymbol));
}
else
{
System.out.println(" " + CurrentState + " " + Tape.substring(CurrentSymbol));
}
}
Iterator<Transition> TransitionsIterator = TransitionSpace.iterator();
while ( TransitionsIterator.hasNext() && foundTransition == false)
{
Transition nextTransition = TransitionsIterator.next();
if (nextTransition.readState.equals(CurrentState) && nextTransition.readSymbol == Tape.charAt(CurrentSymbol))
{
foundTransition = true;
CurrentTransition = nextTransition;
}
}
if (foundTransition == false)
{
System.err.println ("There is no valid transition for this phase! (state=" + CurrentState + ", symbol=" + Tape.charAt(CurrentSymbol) + ")");
return false;
}
else
{
CurrentState = CurrentTransition.writeState;
char[] tempTape = Tape.toCharArray();
tempTape[CurrentSymbol] = CurrentTransition.writeSymbol;
Tape = new String(tempTape);
if(CurrentTransition.moveDirection==true)
{
CurrentSymbol++;
}
else
{
CurrentSymbol--;
}
if (CurrentSymbol < 0)
CurrentSymbol = 0;
while (Tape.length() <= CurrentSymbol)
{
Tape = Tape.concat("_");
}
}
}
if (CurrentState.equals(AcceptState))
{
return true;
}
else
{
return false;
}
}
public boolean addState(String newState)
{
if (StateSpace.contains(newState))
{
return false;
}
else
{
StateSpace.add(newState);
return true;
}
}
public boolean setStartState(String newStartState)
{
if (StateSpace.contains(newStartState))
{
StartState = newStartState;
return true;
}
else
{
return false;
}
}
public boolean setAcceptState(String newAcceptState)
{
if (StateSpace.contains(newAcceptState) && !RejectState.equals(newAcceptState))
{
AcceptState = newAcceptState;
return true;
}
else
{
return false;
}
}
public boolean setRejectState(String newRejectState)
{
if (StateSpace.contains(newRejectState) && !AcceptState.equals(newRejectState))
{
RejectState = newRejectState;
return true;
}
else
{
return false;
}
}
public boolean addTransition(String rState, char rSymbol, String wState, char wSymbol, boolean mDirection)
{
if(!StateSpace.contains(rState) || !StateSpace.contains(wState))
{
return false;
}
boolean conflict = false;
Iterator<Transition> TransitionsIterator = TransitionSpace.iterator();
while ( TransitionsIterator.hasNext() && conflict == false)
{
Transition nextTransition = TransitionsIterator.next();
if (nextTransition.isConflicting(rState, rSymbol))
{
conflict = true;
}
}
if (conflict == true)
{
return false;
}
else
{
Transition newTransition = new Transition();
newTransition.readState = rState;
newTransition.readSymbol = rSymbol;
newTransition.writeState = wState;
newTransition.writeSymbol = wSymbol;
newTransition.moveDirection = mDirection;
TransitionSpace.add(newTransition);
return true;
}
}
}
@aryansharma1305
Copy link

us bhai us ;") @asayaya

Can you please tell how to implement this code

@swapnanilbankura
Copy link

swapnanilbankura commented Oct 30, 2023 via email

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment