Created
May 31, 2012 20:44
-
-
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)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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."); | |
| } | |
| } | |
| } |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| 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; | |
| } | |
| } | |
| } |
swapnanilbankura
commented
Oct 30, 2023
via email
Us bhai us:)
…On Sun, Oct 29, 2023, 10:52 PM aryansharma1305 ***@***.***> wrote:
***@***.**** commented on this gist.
------------------------------
us bhai us ;") @asayaya <https://github.com/asayaya>
Can you please tell how to implement this code
—
Reply to this email directly, view it on GitHub
<https://gist.github.com/NikolasTzimoulis/2846116#gistcomment-4742811> or
unsubscribe
<https://github.com/notifications/unsubscribe-auth/AUMZVN7VZTR3DMKBDJHSN2LYB2GG5BFKMF2HI4TJMJ2XIZLTSKBKK5TBNR2WLJDHNFZXJJDOMFWWLK3UNBZGKYLEL52HS4DFQKSXMYLMOVS2I5DSOVS2I3TBNVS3W5DIOJSWCZC7OBQXE5DJMNUXAYLOORPWCY3UNF3GS5DZVRZXKYTKMVRXIX3UPFYGLK2HNFZXIQ3PNVWWK3TUUZ2G64DJMNZZDAVEOR4XAZNEM5UXG5FFOZQWY5LFU4ZDQNBWGEYTNJ3UOJUWOZ3FOKTGG4TFMF2GK>
.
You are receiving this email because you commented on the thread.
Triage notifications on the go with GitHub Mobile for iOS
<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675>
or Android
<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>
.
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment