i saw this diagram in my textbook for the problem :

Suppose we wish to design a circuit that detects a sequence of three or more consecutive 1’s in a string of bits coming through an input line (i.e., the input is a serial bit stream)

this is the diagram the book suggests .

enter image description here

si means we have read i consecutive 1's from the input (s3 means 3 or more consecutive 1's) and s0 is the start state.

my problem is when we are in state s2 and we read a 1 in input the output is still 0 while it should change to 1.

and also when we are in state s3 and we read a 0 the output is still 1 while it should change to 0.

my mealy implementation (excluding some arcs) is

enter image description here

here we do not have the above problems .

i know the first one is a Moore implementation while the second one is a Mealy implementation .

BUT shouldn't they do the same thing .


Yes, they are the same. In a Moore machine, the outputs are associated with the states, while in a Mealy machine, they are associated with the edges.

This means that a Mealy machine can often have fewer states than the corresponding Moore machine. In this specific example, your states s2 and s3 could be combined, since they have the same set of output edges — you would see this if you were to include the missing edges.

That's not to say that the Mealy machine has fewer flip-flops! In addition to the flip-flops that hold the internal state, each output needs a flip-flop, too. In this example, the Moore machine requires two flip-flops, but the Mealy machine requires a total of three.

  • \$\begingroup\$ what do you mean by " in a Mealy machine, outputs are associated with the edges" \$\endgroup\$
    – KFkf
    Apr 18 '15 at 14:32
  • \$\begingroup\$ if your last paragraph is correct it means Moore machines need fewer flip flops NOT MEALY machines. \$\endgroup\$
    – KFkf
    Apr 18 '15 at 14:38
  • \$\begingroup\$ we need a flip flop in Mealy to make the out put synchronous right? and also can we put a flip flop for the input instead of the out put . \$\endgroup\$
    – KFkf
    Apr 18 '15 at 14:40
  • \$\begingroup\$ but they are not acting the same . e.g. when we are in s2 and we read a 1 in the Moore machine the output changes to 1 after the clock edge . but the Mealy machine does that instantly . i mean in general in a Moore machine the effect of input is not seen until the clock edge . while the effect of input is instantly seen in a Mealy machine. so this makes them act differently . Unless we also make the Mealy machine synchronous by putting a flip flop for the input or the out put . then both circuits act the same. right? \$\endgroup\$
    – KFkf
    Apr 18 '15 at 14:42
  • \$\begingroup\$ No, not right. In the Mealy machine, the edge corresponding to the third "1" on the input is not traversed until the clock edge occurs. This causes the output to go to "1" at the same time it would for the Moore machine. \$\endgroup\$
    – Dave Tweed
    Apr 18 '15 at 14:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.