Design a tiny arithmetic unit. It operates with integers between 0 and 15 (inclusive) that can be
Question:
Design a tiny arithmetic unit. It operates with integers between 0 and 15 (inclusive) that can be represented in binary with 4 bits (from 0000 to 1111). The arithmetic unit stores a single such number x that is initially 0000 and should support the following operations:
• increment: x ← x+1. If the updated value of x exceeds 15 then x wraps around and becomes 0.
• decrement: x ← x−1. If the updated value of x drops below 0 then x wraps around and becomes 15.
• division by 2: x ←bx 2c.
• multiplication by 2 : x ← 2x. If the updated value of x exceeds 15 then x wraps around and becomes 2x−16.
Design a DFA that implements the tiny arithmetic unit described above.
(a) Explain in English your approach to solving the problem. What is the meaning of states? Why did you choose a particular representation? Do you see any alternative approaches?
(b) Write down Σ and the transition diagram of your DFA.
(c) Give a brief argument why your DFA is correct.