Contruct Moore and Mealy Diagram that complement their input

Question

I have been wracking my brain over this all evening. I have to construct 2 diagrams, 1 Moore and 1 Mealy, that complement their own input. Now, I'm aware that Moore Machines are concerned with the input and the output whilst Mealy Machine take the actual state transition into consideration, but I'm clearly missing some point. I have no clue what to do here. Please help!

Answer 1

This is a very interesting problem from a conceptual point of view, because it is simple enough to be solved “by hand”, so such a solution can be compared to the solution obtained using the formal FSM procedure.

Solution 1: “By hand”

Fig. 1(a) shows the circuit ports, where x in the input and y is the output. An obvious solution is depicted in Fig. 1(b), consisting simply of a DFF with inverted input.

Solution 2: Using the formal FSM procedure

A (Moore-type) solution for this problem is shown in Fig. 2(a). Using the formal procedure, the truth table of Fig. 2(b) is obtained for the nx_state, where q (DFF output) represents the present state and d (DFF input) represents the next state; we easily observe (no K-maps needed here) in this table that d=x’. The truth table for the output is in Fig. 2(c), from which y=q is obtained. The resulting circuit is then that of Fig. 2(d), drawn following the traditional FSM model (all combinational logic in the upper section, all DFFs in the lower section). Comparing it to that in Fig. 1(b), we observe that they are indeed equal.

Solution 3: Using a Mealy machine

Converting the Moore machine of Fig. 2(a) into a Mealy machine, Fig. 3 results. Since this is a single-state machine, it is indeed a combinational circuit. (Just build the truth tables and draw the resulting circuit; a “dummy” DFF should result, because the output must now be asynchronous.)

Answer 2

The core idea for the Moore machine is to have two states: a “one was read, output zero” and a “zero was read, output one”. You go from one to the other by reading one or zero, respectively. You'll note that with the formal definition, there is always a “delay” between input and output. It's also not possible to avoid outputting an arbitrary initial symbol.

The Mealy machine implementation can actually be reduced to a single state, since each output symbol only depends on the corresponding input symbol. The transitions are then trivially: “read one, write zero” and “read zero, write one”.