How to implement a sequence detector to detect multiple sequences?

Question

I'm working on a problem of implementing a sequence detector that outputs 1 whenever I detect 0010 or 100. What disturbs me is the 0010 'or' 100 part. I know how to implement a single sequence detector - if I only have to detect 0010, I only need 4 states and after the 4th state I go back to the 2nd state with (0/1) and so on:

State A (0/0)-> State B (0/0)-> State C (1/0)-> State D (0/1)-> back to State B and so on..

However, I also have to detect 100. I see that for 0010 if I add 0 in the end, I get 00100, which is both 0010 and 100 at the same time. So in the case where I get 0 after state D, should I go back to state B with 0/0? But then I already went back to state B (from state D) with 0/1 so the two 0's overlap.

• Dwayne Reid: The easiest method is to have separate state machine detectors that detect each sequence, then OR the outputs of the detectors together. But that may be regarded as not the answer that is requested.
• michaelkiko: yes.. I also thought about that but yeah i guess its not correct
• Andy aka: Why do you say "100" with no leading "0" digit but you say "0010" instead of "10"?
• michaelkiko: sorry I didn't get what you said Andy. I'm trying to implement a sequence recognizer so that it outputs 1 whenever a sequence of input bits ends in 0010 or 100.
• Majenko: So you mean 0010 or x100 to keep the bit size the same? x = "don't care".

Answer 1

Recognizing a sequence of symbols is known as "lexical analysis", or more colloquially, "scanning" or "lexing". It's actually a huge topic in software, where an input grammar needs to be broken into meaningful tokens as efficiently as possible. There's a whole process that involves writing a formal grammar for the sequences to be recognized, converting that grammar first to a NFA (nondeterministic finite automaton) and then to a DFA (deterministic finite automaton). The DFA can be described by a table of state transitions that drives a relatively simple and efficient interpreter.

Your problem is a vastly simplified version of that — only two symbols and just two fixed sequences that need to be recognized. It should be solvable pretty much by inspection, without requiring all of the formalism described above.

Just start drawing state diagrams for recognizers for the sequences individually, then look for common sub-sequences and valid end states as you try to combine them into one master state machine.

Here's the diagram that I came up with:

state diagram

The states across the top are the recognizer for "0010", with the final transition that has the output "1" going down to the "10" state, since the last part of this pattern corresponds to the first part of the "100" pattern. Similarly, the states across the bottom are the recognizer for "100", with the final transition going to the "00" state in the top row.

• michaelkiko: Thankyou! So for 0010, I did it like this: State A (0/0)-> State B (0/0)-> State C (1/0)-> State D (0/1)-> back to State B For 100, im not sure where to go from state A because if I detect 1 and move to state B then it doesn't make sense because I already stated that if I detect 0, i move to state B. so maybe for 100 detection, I should start from state D?
• Dave Tweed: No, state A is your start state. If you get a 1 first, you definitely need to move to a different state (other than B). It may help to label each state with the bit sequence that has been recognized "so far" when in that state.
• michaelkiko: okay so I will use 6 states in this problem: 000, 001, 010, 011, 100, 101, 110. And i assume if I get 1 first , i should move to 110 (state 6)? this is part that I'm confused.. is there a specific rule for this?
• Dave Tweed: See the diagram above.
• michaelkiko: wow thank you for your effort.. I will try to understand the diagram for my own for few minutes. Can I ask you later if I have further question?

Answer 2

Yes, the 6 states should be 000, 001, 010, 011, 100, 101, 110. 000 represents the beginning, 001 represents when you have recognized '0', 010 for '00', 011 for '001', 100 for '1', 101 for '10'. When the input is 0, it should always point to state 001; also, from state from 011, it should point to 001 with output of 1. When the input is 1, it should always point to the state 100; also, from state 010, it should point to 100 with output of 1. I hope it's not worded too complicatedly.

enter image description here

• michaelkiko: yeap :D I edited my question a bit because I just said way to much things blah blah so others might had hard time reading it. I only left essential parts. Anyways, I'm just trying to analyze it by myself now and you mean with state 010 (with 1/0), it should point to 101?
• HowardD: Oops, accidentally deleted my comment.. I meant from state 010 it should point to 100 with 1/0. Also, states 011 and 100 should point to 001 with 0/1, 0/0, respectively.
• michaelkiko: hmm the above diagram says when I have 011 with output of 0 so (1/0) I should point to 100. I'm kind of confused now..
• michaelkiko: For 010 with 1/0, isn't it supposed to be point to 011 because I also want to detect 0010? Am I understanding something incorrectly here?
• HowardD: To clarify, for state 010 ('00' detected), it should point to both 011 and 100 with 1/0.