If you want to copy all the files at once, get this zip file:
To run the simulator, get the four java files:
Here is a sample input file: in.txt
The format of the input is as follows:
<Name of start state> <current state> <current symbol> <next state> <head instruction> ... <current state> <current symbol> <next state> <head instruction> $ <input string w1> <input string w2> ...
This java program will simulate the Turing machine on input w. I don't have much error detection with respect to the input, so please check your formatting carefully. If you have more than one transition for a state/symbol pair, the TM will choose to execute the first one you typed in and will always ignore any other ones. Please let me know asap if you run into any problems with the simulator- this is the first time I am using this version. The TM's from the previous text worked differently.
The sample input file in.txt contains:
s // start state is s // Machine OO: Created by Wendy Myrvold. // This machine halts in state h when there is an odd // number of a's and an odd number of b's in the input // and it hangs in state hN otherwise (due to no transitions defined). s # ee L ee a oe L // State ee means both a's and b's are even ee b eo L // State ee means both a's and b's are even eo a oo L // State eo means even a's and odd b's eo b ee L // State eo means even a's and odd b's oe a ee L // State oe means odd a's and even b's oe b oo L // State oe means odd a's and even b's oo a eo L // State oo means both a's and b's are odd oo b oe L // State oo means both a's and b's are odd // When we see the # at the RH end of the input we are done. oo # h # oe # hN # eo # hN # ee # hN # // This is the end of the TM $ // Try it on w not in L abbbaabaa // Try it on w in L ababab
To run it I use this (on a unix machine):
javac *.java java TM < in.txt > out.txt
This give you text-based output suitable for handing in with your assignment.
The program uses stdin and stdout but this makes it take the input from the file in.txt and put the output in the file out.txt.
You can do something similar on a Windows or a MAC (using the < to get input from a file instead of stdin and using > to put the output into a file). Ask for help from me or a consultant if you do not know how to do this. You don't want to keep typing in your TM programs each time you want to try running them!
Here is the output you should get from in.txt:
The TM:
Start state for the TM: s // start state is s
: STATE S STATE HEAD
// Machine OO: Created by Wendy Myrvold.
// This machine halts in state h when there is an odd
// number of a's and an odd number of b's in the input
// and it hangs in state hN otherwise (due to no transitions defined).
Rule 1: s # ee L
Rule 2: ee a oe L // State ee means both a's and b's are even
Rule 3: ee b eo L // State ee means both a's and b's are even
Rule 4: eo a oo L // State eo means even a's and odd b's
Rule 5: eo b ee L // State eo means even a's and odd b's
Rule 6: oe a ee L // State oe means odd a's and even b's
Rule 7: oe b oo L // State oe means odd a's and even b's
Rule 8: oo a eo L // State oo means both a's and b's are odd
Rule 9: oo b oe L // State oo means both a's and b's are odd
// When we see the # at the RH end of the input we are done.
Rule 10: oo # h #
Rule 11: oe # hN #
Rule 12: eo # hN #
Rule 13: ee # hN #
// Try it on w not in L
Input 1 computation: w of length 9=[abbbaabaa]
Step 0 : (s, #abbbaabaa[#])
Step 1 : (ee, #abbbaaba[a])
Step 2 : (oe, #abbbaab[a]a)
Step 3 : (ee, #abbbaa[b]aa)
Step 4 : (eo, #abbba[a]baa)
Step 5 : (oo, #abbb[a]abaa)
Step 6 : (eo, #abb[b]aabaa)
Step 7 : (ee, #ab[b]baabaa)
Step 8 : (eo, #a[b]bbaabaa)
Step 9 : (ee, #[a]bbbaabaa)
Step 10 : (oe, [#]abbbaabaa)
Step 11 : (hN, [#]abbbaabaa)
No valid transition, TM hangs.
End computation 1
// Try it on w in L
Input 2 computation: w of length 6=[ababab]
Step 0 : (s, #ababab[#])
Step 1 : (ee, #ababa[b])
Step 2 : (eo, #abab[a]b)
Step 3 : (oo, #aba[b]ab)
Step 4 : (oe, #ab[a]bab)
Step 5 : (ee, #a[b]abab)
Step 6 : (eo, #[a]babab)
Step 7 : (oo, [#]ababab)
Step 8 : (h, [#]ababab)
Halts because the state is final.
End computation 2
If you prefer to run it with the visual interface as demonstrated in class:
javac *.java java JTM
The TM is loaded using the New TM button to select the file which contains the TM description. The initial w will be the first one which you include after the $ (or empty string if the input is missing). Click on Input to type in alternate input strings. You have to click on the Run button to start the TM program running or can use the + button to just execute one step at a time. The slider controls how fast the TM runs.
Other Examples: