Problem-2
Draw a Turing machine to find 2βs complement of a binary number.
2βs complement of a binary number is 1 added to the 1βs complement of the binary number.
Example:
Approach:
- Start from the end of the input string.
- Pass all consecutive β0βs.
- When you encounter the first β1β, do nothing.
- After that, replace β1β with β0β and β0β with β1β.
- Stop when you reach the beginning of the string.
Intuition:
Whenever a numbers 1βs compliment is taken and 1 bit is added to its LSB (Least Significant Bit), all the 1βs (which were originally 0) appearing together from right will add with the carry and change back to 0. Since the first encounter of 0 in 1βs compliment string (which was originally 1) , every β1β bit to its right, if any, will add 1 and change to 0. The first encountered 0 in the string will add 1 and change back to 1, as in the original string. This does not impact any further bit to its left, thus final string have
- all 0βs same to the right of 1st β1β bit encountered ( ( complement of 0) + 1) = 0 + carry(=1) to its left element)
- the 1st β1β bit encountered will also revert back to 1 the same way.
- All other bits to its left will be flipped without any restrictions.
States:
- q0: Initial state
- q1, q2: Transition states
- q3: Final state
Symbols:
- 0, 1: Binary digits
- B: Blank symbol
- R, L: Right and left movements
Steps:
- In state q0, move right until you encounter a non-blank symbol. Transition to state q1.
- In state q1, continue moving right until you encounter the first β1β. Transition to state q2.
- In state q2, replace β1β with β0β and β0β with β1β. Move left.
- When encountering a blank symbol, transition to state q3.
- In state q3, move right until you reach the end of the string. Halt the machine.
- Here, q0 shows the initial state and q1 and q2 shows the transition state and q3 shows the final state.
And 0, 1 are the variables used and R, L shows right and left.
Explanation:
- Using state βq0β we reach end of the string.
- When BLANK is reached move towards left.
- Using state βq1β we passes all 0βs and move left first 1 is found.
- Pass single β1β and move left.
- Using state βq2β we complement the each digit and move left.
- When BLANK is reached move towards right and reaches the final state q2.
Turing machine for 1βs and 2βs complement
Prerequisite β Turing Machine, 1βs and 2βs complement of a Binary Number
Contact Us