= Solution
The <finite-state machine> retains its state on input `00` or `11`, moves to `Lt` on `01`, and moves to `Gt` on `10`. Here each input label is the pair `ab`, not a pair of outputs. The following <state-transition diagram> shows every valid-state transition; a diagonal input is stronger than all previous comparison history because it arrives at a more significant position.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2003/computing-prelims-2003-comparator.png]
{title=Least-significant-first comparator transitions and Karnaugh maps}
Equivalently the complete transition rule is
$$
\boxed{\delta(s,a,b)=\begin{cases}\mathrm{Lt}&a=0,\ b=1,\\
\mathrm{Gt}&a=1,\ b=0,\\
s&a=b.\end{cases}}
$$
The <state-transition diagram> starts at `Eq`, representing the comparison of two empty, hence zero-valued, bit strings.
Back to article page
