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.