This homework asks the student to develop two Turing machines, the descriptions of which must be in the format expected by the constructor of the TuringMachine class mentioned above. This format is described in comments found within that class and is exemplified by the contents of these two files:
Your Turing machines should be designed under the assumption that they begin execution with the read/write head scanning the tape square holding the leftmost symbol of the input string. In each case, make state 1 be the initial state.
1. Devise a Turing machine that accepts the language
consisting of those strings (over {a,b}) having the same number of a's as of b's. Make state 0 be its final/accepting state (meaning that state 0 should have no "outgoing" transitions). Submit a description of your Turing machine in a file named tm_equal_ab.txt.
2. Devise a Turing machine that translates unary numerals into their corresponding binary numerals. Use {a} as the input alphabet so that, for example, the string aaaaa (consisting of five a's) represents the number five. It would be preferable if your Turing machine halted with no symbols other than 0, 1 and the blank (-) on the tape, with the machine's read/write head positioned at the leftmost bit.
Recall that to increment a binary numeral, you flip its rightmost zero and all bits to its right. If there are no zeros, you flip all bits and prepend a one to the front. Examples: 1010111 becomes 1011000 and 1111 becomes 10000. Submit a description of your Turing machine in a file named tm_unary_to_binary.txt.
Hint: Use the portion of the tape to the left of the input string for forming the binary numeral.
Note: Due to the manner in which the TM_App2 program works, to specify the empty string as input, you would tell the program (in answering its prompt) that the input string is - (a single dash/hyphen, which is the character used for the BLANK).