How to design a finite state machine to detect 0110 in the input?

Question

My task is to design a FSM whose output goes high for a single cycle whenever the pattern 0110 is detected on its input. The patterns may overlap, so an input 0110110 of would cause the output to go high twice- once for the first pattern (0110110), and once for the second pattern (0110110). a is used for the input and f is used for the output.

I am assuming I will need five state bubbles like this.

Is this correct or am I missing some cases based on the pattern going high twice if the pattern overlaps?

• Joey Eremondi: The idea of output going "high" or "low" is probably not particularly familiar to Computer Scientists. I suspect most people here learned finite automata in terms of acceptor machines, reading in a string then either accepting or rejecting it. Are you using this for circuit/electrical design?
• D.W.: Possible dup: cs.stackexchange.com/q/11780/755
• reinierpost: @jmite: I know Computer Science is not about computers, but let's be honest: we know that much. At least I do :)
• Joey Eremondi: It depends highly on the type of CS education, particularly whether a school does it as part of science or engineering. I'm not saying it's off topic, I'm just asking for some background.
• David Richerby: This is certainly not a duplicate of a question about nondeterministic finite automata: the asker seems to be looking for a circuit design and real electronic circuits are not nondeterministic. I also don't think the question is unclear so I'm voting to leave open.

Answer 1

It looks like you're missing the overlap case, if I understand your diagram correctly. This does the trick:

A // goto B if read 0 else stay
B // goto C if read 1 else stay
C // goto D if read 1 else goto B
D // goto E if read 0 else goto A
E // emit rising edge, goto B

assuming that you have a falling edge after every read.

Answer 2

This problem is just an instance of the substring searching problem, for the specific substring 0110ドル$. There are several algorithms that solve it.

Given that the search is to be done in real-time, I guess the best algorithm is the Knuth-Morris-Pratt algorithm. For any string to be searched, the KMP algorithm will compute the table for a DFA that recognizes all occurences of that string in any string given as input.

Note however that the finite state device to be constructed is not really a DFA, but a deterministic finite state transducer (also known as Generalized sequential machines - GSM), as it has an output for each transition, which is either low or high. The words low and high may be taken as symbol of an output alphabet, even if they have physical meaning in the context of the question.

I leave it as an exercise to apply the KMP algorithm to the specific example of the question, since the question is actually asking how to design the finite state transducer, and is not asking to actually do it.