y(n) = 1 if number of 1's = number of 0's in u(0), u(1),
... , u(n-1)
y(n) = 0 if number of 1's ¹ number of
0's in u(0), u(1), ... , u(n-1)
It is possible to
prove that Equal cannot be implemented by a finite state machine.
Outline: Suppose that an M-state FSM implements equal, and
then give it an input with M+1 1's. Observe that one state
must be visited more than once. Suppose that n-th and
m-th states visited are the same,
where n is not equal to m. Then n successive 1's leave
the machine in the same state as m successive 1's.
These two sequences are therefore indistinguishable.
Thus, if the machine detects that 1n0n
has an equal number of 1's and 0's, then it would have to conclude
that 1m0n also has
an equal number of 1's and 0's, which is wrong.