# Infinite State Machines

Build state machine *Equal* that outputs

*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)

*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

^{n}0

^{n}has an equal number of 1's and 0's, then it would have to conclude that 1

^{m}0

^{n}also has an equal number of 1's and 0's, which is wrong.