I was reading about finite state machines. I read about Moore and Mealy machine and also the state representation. I read that in the Moore machine the output depends on the present state only and in the Mealy machine the output depends on input and present state. But I don't understand how this could vary the number of states?
If you're in state A and input X happens, how do you output Y?
A Moore machine must transition to state B whose sole purpose is to output Y, then back to A.
A Mealy machine can simply transition back to A whilst outputting Y
Thus a Moore machine requires more states. You need at least one state for every combination of outputs your machine requires.
The more information or Bandwidth there is to determine the next state the fewer states or cycles that are required to complete the entire sequence.
This why DDR2,3,4,5,6,7,8 works faster by using transitions splitting the clock into N phases for parallel operations with N ports combined into 1. Thus the bandwidth is multiplied by the number of inputs added to the present state in this case split into equal phases.
By combining the present state with input you are adding more information and also entropy with the randomness of input states so when added with transitions and polarity of transitions, this extends the bandwidth greatly and allows more complex but fewer Mealy states to realize.
Complexity does not always mean hard to do, it just means more static and dynamic inputs with edge detection logic may be included to reduce the cycle time, latency or registers required.