RSS Feed (xml)
It’s time for puzzle #7.
An FSM receives an endless stream of “0″s and “1″s. The stream can not be assumed to have certain properties like randomness, transition density or the like.
Is it possible to build a state machine, which at any given moment outputs whether there were more 0–>1 or 1–>0 transitions so far?
If yes, describe briefly the FSM. If no, give a short proof.
