Discussion
Consider the TM described below for computing 2’s complement using a transition diagram. In this diagram few of the transition input entries are missing and are denoted by I, II and III.
Here L represents left, R represents right and N represents Accept (No movement)
Which of the following is exact replacement for I, II and III above in the order.
Answer: A
The missing entries are (0, 1, N), (B, 1, N), (1, 0, L).
The two's complement of a binary number is its ones' complement plus 1. In state q0 the machine moves right inverting every bit, (0, 1, R) and (1, 0, R), which forms the ones' complement. At the blank after the number it turns back left into q1.
In q1 it adds 1 starting from the rightmost bit. A 1 plus 1 gives 0 with a carry, so it writes 0 and keeps moving left: III = (1, 0, L). A 0 plus the carry gives 1 with no further carry, so it writes 1 and accepts: I = (0, 1, N). If the carry runs past the leftmost bit onto the blank, it writes 1 there and accepts: II = (B, 1, N).
The other options either do not write the carry correctly or move right, away from the bits still to be processed.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development