sequence detector

Thread Starter

mo2015mo

Joined May 9, 2013
157
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.. ;)
 

Attachments

tshuck

Joined Oct 18, 2012
3,534
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.
 

WBahn

Joined Mar 31, 2012
29,976
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.
 

WBahn

Joined Mar 31, 2012
29,976
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.
 

Thread Starter

mo2015mo

Joined May 9, 2013
157
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.
OK, i.e. must build the state table and filled it from this state diagram ??
 

WBahn

Joined Mar 31, 2012
29,976
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.
 

tshuck

Joined Oct 18, 2012
3,534
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
 
Top