I'm having difficulty with a seemingly simple question. "Is it possible to have a finite state machine that detects if a bit string of arbitrary length has the same number of zeros as ones? If so what would it look like"? In trying to solve this problem I have come up with a variety of finite state machines. However, none have been able to solve the problem for a bit string of arbitrary length.
Any suggestions? Thank you!
Best Answer
The number of $1$'s in the first $n$ bits of input may be any integer from $0$ to $n$, and if there are at least $n$ more bits to go, in order to determine the result the FSM would need to "remember" which of those integers it is. Thus at least $n+1$ states are needed for a FSM that can do this with $2n$-bit strings. Since the size of the input string is arbitrary, no such FSM is possible.