# How to determine what the states should be in this state diagram

I'm trying to make a simple state diagram to understand a concept in class. There is one input and one output $\left(X \ \text{and}\ Y\ \text{lets say} \right)$. The output is $1$ if an input is false after exactly two true inputs. For example, $Y=1$ if the last three inputs were $110$. In all other cases, the output should be $0$.

I'm having trouble deriving what the states themselves should be (as in, the bubbles in the diagram). Once I figure that out, I can easily apply the input/output conditions. I tried setting the states to represent the current bit ($1$ or $0$, so two states), but that didn't work.

You didn't specify whether the state machine was of Mealy or Moore type, so I included them both below: • Ahhh so the states would represent the last two inputs, seeing as after adding a third one we can tell what the output needs to be. This makes so much more sense now, thanks! – n0pe Nov 23 '13 at 23:55
• Not necessarily; it just happened that the states matched the last two inputs, interchanging the states between the bubbles has no impact on the proper functioning of the machine, it just causes different circuit wirings. – K. Rmth Nov 26 '13 at 18:07

Define your initial condition in the 1st bubble with input X and output, Y

With 3 sequences in time one bit can present 8 different patterns thus 8 bubbles are the maximum required. But since only 1 combination produces an output, you can simplify or share bubbles that do not lead to a possible output in the next state one or two states and return to a shared state.

In your case Y=1 only if past inputs were 110.

• Thus in bubble S0, if X=0 it stays in S0 and goes to S1 if X=1
• Then in S1, X=0, it goes back to S0 or else X=1 it goes to S2 bubble.

And so forth..