enter image description here

And Here is the answer, can you explain me specifically? I really dont know how to draw this graphical FSM graph.
enter image description here

Best Answer

Just like writing computer programs, good descriptive choice of variable names helps. Nobody would use 'a' as a variable name in code these days (I hope, or if they did, wouldn't expect to understand it a month later), they'd tend to use 'cars_per_hour', or 'creation_date', something meaningful.

Likewise for state machines. It's much easier to 'play computer' if we have meaningful state labels.

The task is to spot three consecutive 0s. How do we do that? We spot a single zero three times, and remember where we are in the process. How do we remember? For this question we are asked to use a state machine.

Let's have a state 'no_zeroes_seen_yet'. We start in that state, and go to it any time we see a '1'. Another state would be 'one_zero_seen'. We move to that state if we are in 'no_zeroes_seen_yet' AND we see a '0'. Another state would be 'two_zeroes_seen'. How do we get there?

Relabel the 'a', 'b' and 'c' states of the suggested answer with these more meaningful labels, and see if that helps.

I notice the answer leaps on to code these three states with A and B binary bits, which I feel is a bit premature. I would never conflate these steps, first getting to a pure logical FSM diagram, and then handling the implementation later (just like premature optimisation militates against clear code!).

FWIW, a 'one-hot' implementation is far easier to deal with, maps better onto VHDL and code, but is uses more D-flops. Again, similar arguments contrasting clarity and 'efficiency' are raised for and against compilers!

Do we have a 'three_zeroes_seen' state, or do we rely on 'two_zeroes_seen' AND another '0' to mean the same thing? That's the difference between Mealy and Moore styles, it's important to know which style is required. The suggested answer appears to assume Mealy without comment. Mealy tends to be smaller and more 'efficient'. Try reading about 'Mealy machine' on wikipedia.

Re-reading the question, the 'minimal' word is directing you to use a binary-coded Mealy machine, though I would still design it behavioural first, implementation second.

Related Topic