# sequence detector

Discussion in 'Homework Help' started by mo2015mo, May 21, 2013.

1. ### mo2015mo Thread Starter Member

May 9, 2013
157
1
HI Guys ,

I have been having problem with the attached question , I have tried solve it as attached (fig22).

Is this solution correct? IF Not ..why and what the correct solution..

File size:
260.8 KB
Views:
82
2. ### tshuck Well-Known Member

Oct 18, 2012
3,531
675
I think the question may be asking does you to derive a circuit, but otherwise reasonable. If you look at the FSM chapter in the ebook, it shows a good way to describe the state table and use it to make a Moore FSM.

3. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
You can't determine what the sequence is that it is detecting because there is no accepting state identified, unless we interpret the output of 1 on the transition from F to C as indicating acceptance. Which is probably reasonable. But if so, then 00101 is not the only string it will accept, merely the shortest.

The language recognized by this Finite Automaton is actually pretty convoluted (not to mention infinite).

But I agree with tshuck and think that you are simply being asked to design an FSM that implements this transition diagram. To implement this, you will need to use a Meely Machine since the output depends on both the current state and the current input.

4. ### mo2015mo Thread Starter Member

May 9, 2013
157
1
Could you guide me about my mistake?

5. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
What mistake?

We've told you that we believe the answer is looking for an implementation of a finite state machine that executes the supplied diagram. That's the only "mistake" that it appears you have made thus far.

6. ### mo2015mo Thread Starter Member

May 9, 2013
157
1
OK, i.e. must build the state table and filled it from this state diagram ??

7. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
That would be the most reasonable approach, I believe.

8. ### mo2015mo Thread Starter Member

May 9, 2013
157
1
i find the state table as attached fig33 , How can i get the sequence ...??

File size:
234 KB
Views:
43
9. ### WBahn Moderator

Mar 31, 2012
18,093
4,920
The method you used found the shortest acceptable sequence, but there are infinitely many sequences that will be accepted. Deriving the regular expression for them is fairly straightforward, but more properly in the realm of finite automata. As a teaser, the regular expression

1*(01)*0*00*(101)*

Is regular expression for a subset of the strings that are recignized.

The * operator means that the thing immediately to the left can appear zero or more times. So let's just have each of the * operators result in two copies. That makes the string

1* (01)* 0* 0 0* (101)*

11 (01)(01) 00 0 00 (101)(101)

11010100000101101

If you run that through the machine, you should find (assuming I ddin't mess something up) that the last transition asserts a HI output.

10. ### tshuck Well-Known Member

Oct 18, 2012
3,531
675
Ah yes, I seem to have overlooked the location of the output, you need a Mealy machine, not a Moore...

A Moore machine's output is determined only by its state, a Mealy, on the other hand, had its output dependent on both state and input. You can tell because the output is shown on the transition from one state to the next.

I write an article doing a sequence recognizer with a Mealy machine that you might find helpful. It is still (?) pending review, do you can see it in the thread here:http://forum.allaboutcircuits.com/showthread.php?t=82082