"11" overlapping sequence detector using mealy machine

Question

Design a sequence detector that detects two or more consecutive 1’s in an input stream of bits (as in 01110111100) using a Mealy machine and T flip flop.

I have made the state diagram and the final state equations but I have no way to verify them. What corrections, if any, are required?

• greybeard: There are simulators to help visualising (/internalising) the workings of abstract machines as well as T-FFs&gates.
• devnull: Don't forget the premise that X should be synchronized for this to work properly as a Mealy FSM

Answer 1

That looks good! You might want to define (separately) what the initial state is, A or B.

To test such a system, you'd need to test all state transitions being correct. So, you'd create test sequences that bring you in either state (which is easy here, a 0 brings you into state A, and a 1 brings you into state B, and there's no more states than these two) and then you try all possible state transitions from these states (so, that's also just 2 each), and see whether their output is correct. So, that's really just trying four different input sequences (00, 01, 10, and 11) and noting down whether they work.

Why don't you need to test longer sequences? Because state diagrams like yours have Markov property, i.e., what happened before doesn't matter; the only thing that matters is in which state you are now. So, once you've tested every single state transition, i.e., every arrow in the diagram, you've exhaustively tested the state machine design. That's true for every state machine constructed this way, and gives you a method to test all of them, not just this simple one!