CS 375 HW 4

You can download JFLAP or run the demo applet.You will want to look at the tutorial for finite automata, and for Turing machines. You will create single-tape Turing machines, and test them.
Each input should be a binary string followed by an end-of-string marker.

To submit:

• A printout of the TM, from the JFLAP layout;
• a description of what the states "mean" (think of it as commenting your code);
• a list, possibly hand-written on the side of the printout page, of at least 5 strings on which you tested your TM.

• Write a Turing machine that takes a binary string s and increments it by 1. Note that there are issues with treating either end as the least significant bit. State, clearly, on your submission which you chose.
• Write a Turing machine that takes a binary string s and finishes with the string written backwards. For instance, if the input is 1000111, the TM should halt with 1110001 written on the tape.

One way to invert a string is to break the computation into two passes: one to represent the backwards string with other symbols, say 2s and 3s, and a last pass to rewrite the symbols back to 0s and 1s. The book's discussion of Markov algorithms suggests a different method.