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.. ;)
     
  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
    17,757
    4,799
    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
    17,757
    4,799
    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
    17,757
    4,799
    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 ...??
     
  9. WBahn

    Moderator

    Mar 31, 2012
    17,757
    4,799
    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
     
Loading...