so I have this problem given to me at my university, and I'm really lost about it, I don't know if you can help me cause this is not strictly code, I think I have to doit with digrams and tables by hand.
So, the problem is to design a Turing machine that calculates the parity of a binary number. If the number of 1's is pair add a 0 at the end, if it is unpair add a 1 at the end.
Example
a) 001001 -> 0010010
b) 101010 -> 1010101
Hoping you can help me, thanks
Input: a string x of binary digits
Output: xd where d id 0 if #1(x) is even and 1 if #1(x) is odd, where #1(x) is the number of instances of 1 in x.
Design: we will scan the string from left to right, keeping track of the parity of the number of instances of 1 seen so far. When we run out of input, we will see which state we are in, write the corresponding final digits, and then halt-accept.
Implementation:
q t q' t' d comment
q0 0 q0 0 right see a zero, stay in state and keep looking
q0 1 q1 1 right see a one, now we've seen odd number, keep looking
q0 B ha 0 same ran out after seeing even number
q1 0 q1 0 right see a zero, stay in state and keep looking
q1 1 q0 1 right see a one, now we've seen an even number, keep looking
q1 B hA 1 same ran out after seeing odd number