# Finite State Machine

My task is to design a FSM whose output goes high for a single cycle whenever the pattern 10110 is detected on its input. I am assuming I will need five state bubbles.

• We're not here to do your homework for you. Commented Jul 25, 2013 at 3:48

State 0 is only needed immediately after reset. A 0 in state 2 should go back to state 1, and state 4 should go back to state 1 immediately after emit. Also, you have 2 transitions for state 3 on a' (only the one to state 4 is needed).

A lot harder than I thought it would be. And even this is probably more complex than it needs to be. State 4 indicates a match.

• Thank you. What does the emit mean in state 4? Would that be a'? Commented Jul 24, 2013 at 21:40
• That would be emitting 1 on the output. Commented Jul 24, 2013 at 21:50
• Ah, alright. So what input would I have on state 4 going to state 1? Or would I just draw an arrow? Commented Jul 24, 2013 at 21:51
• There wouldn't be an input for it; it would be an automatic transition. We need to separate out state 4 explicitly since we can't have an emit on every entry to state 1 (e.g. 0 -> 0). Commented Jul 24, 2013 at 21:53
• That will fail to match 0110110. Commented Jul 24, 2013 at 22:02
       |    1         0
-----------------------
INITIAL|    1   INITIAL
1 |    1        10
10 |  101   INITIAL
101 | 1011        10
1011 |    1     10110
10110 |    -         -


I cant post pictures, so I chose to fall back to 'table' version of the FSM (if you reconstruct the picture from it, everything would be clear).

Left-most column in the table represents possible states (6 in total - INITIAL,1,10,101,1011,10110), top row represents possible inputs (0 and 1). Content of the table represents transition from one state (left column) to another state under given input (top row).

explained: You start and wait in INITIAL state reading any 0s that come in.

When you hit 1, you transit to state 1 then you continue from there in similar fashion ... Basically the names of the states represent the longest "good" read part of the input, but this is only for better orientation, you could name the states whatever you want. State 10110 is final. If you reach it, you should fire the signal or whatever.

Here is a catch in your question, though: you havent specified if you just want to fire the signal every time the last 5 digits are 10110, or if you want to 'reset the counter' after you find that sequence.

Therefore you can add transition from state 10110 to 101 under 1 and to INITIAL state under 0, if you want to fire a signal every time "the last 5 digits on input were 10110".

Otherwise add transition from state 10110 to INITIAL state under both 0 and 1 (that means "forget everything you read so far and start again").

Although Ignacio Vazquez-Abrams' answer is close, it fails if 0110 is input from start.

• This will not accept 110110 Commented Jul 30, 2022 at 20:04