Infinite State Machines
Build state machine Equal that outputs
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 1
n0
n
has an equal number of 1's and 0's, then it would have to conclude
that 1
m0
n also has
an equal number of 1's and 0's, which is wrong.
Up to Topics
Previous
Next