Page 1 of 2 12 LastLast
Results 1 to 15 of 21

Math Help - Machine Of Mealy And Moore

  1. #1
    Super Member
    Joined
    Jun 2008
    Posts
    829

    Machine Of Mealy And Moore

    As from a Mealy machine to determine an equivalent Moore machine? And unlike?

    The Mealy machine:

    q0 -> (b,0) -> q0
    q0 -> (a,1) -> q1
    q1 -> (b,0) -> q1
    q1 -> (a,1) -> q2
    q2 -> (a,1) -> q1
    q2 -> (b,0) -> q2

    q2 is final state

    How do I find an equivalent Moore machine?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    As from a Mealy machine to determine an equivalent Moore machine? And unlike?

    The Mealy machine:

    q0 -> (b,0) -> q0
    q0 -> (a,1) -> q1
    q1 -> (b,0) -> q1
    q1 -> (a,1) -> q2
    q2 -> (a,1) -> q1
    q2 -> (b,0) -> q2

    q2 is final state

    How do I find an equivalent Moore machine?
    I drew a diagram. Sorry for the messiness but I'm not set up for making nice-looking state machine diagrams quickly.



    Looks like this machine accepts strings over {a,b} with the number of 'a' positive and even. The output is just a 1 whenever there is an 'a', and a 0 whenever there is a 'b'.

    Here's what I came up with for a Moore machine.

    EDIT: I changed the Moore diagram a couple times, I think it's right now.

    Attached Thumbnails Attached Thumbnails Machine Of Mealy And Moore-mealy.png   Machine Of Mealy And Moore-moore2.png  
    Last edited by undefined; June 20th 2010 at 01:38 PM. Reason: typo
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Jun 2008
    Posts
    829
    What have you done to find Moore diagram ? Which step in turning Mealy in Moore ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    What have you done to find Moore diagram ? Which step in turning Mealy in Moore ?
    My method isn't as systematic as you might like. I just looked at what the Mealy machine did, and duplicated the functionality by creating a Moore diagram "from scratch." I would have to think more about a general method to convert between the two; this thread (on another forum) might be of use.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Jun 2008
    Posts
    829
    First you find a language that Mealy generates? What is the language that the Mealy diagram generated ?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    First you find a language that Mealy generates? What is the language that the Mealy diagram generated ?
    Well for any input string over {a,b}, the Mealy machine generates an output and also either accepts or rejects the string. The set of accepted strings is the language: All strings over {a,b} such that there are a positive even number of 'a' characters. The output is just the original string with all 'a' replaced by 1 and all 'b' replaced by 0. So for example, given

    input: abbbaaaba

    we get

    output: 100011101

    and when the machine halts because there are no more input characters, the machine is in a non-accepting state, so string abbbaaaba is not in the language (there are an odd number of 'a' characters). So I just went with this.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Super Member
    Joined
    Jun 2008
    Posts
    829
    All entries are a or b and all outputs 1 or 0?


    I can do:
    Attached Thumbnails Attached Thumbnails Machine Of Mealy And Moore-imagem.jpg  
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    All entries are a or b and all outputs 1 or 0?


    I can do:
    Well the Moore diagram you attached always prints out a 1 at the beginning, which is a problem. Also, you didn't specify what happens when we're in state q1 and the input is b. Also consider the input bbbaaa. This gives output 1111101, but it should be 000111. Do you agree?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Super Member
    Joined
    Jun 2008
    Posts
    829
    What I do not get it in your diagram is that it has alpha in q0. what the alpha ?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    What I do not get it in your diagram is that it has alpha in q0. what the alpha ?
    Oh that's a lambda. It means don't print any output.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Super Member
    Joined
    Jun 2008
    Posts
    829
    Quote Originally Posted by undefined View Post
    Oh that's a lambda. It means don't print any output.
    Friend, I still do not understand
    Starting at q0
    In Mealy
    q0 -> (b,0) -> q0
    q0 -> (a,1) -> q1

    You're not sending anything to own q0
    b to q1. But not is to q0 ?
    a to q2. But not is a to q1 ?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    Friend, I still do not understand
    Starting at q0
    In Mealy
    q0 -> (b,0) -> q0
    q0 -> (a,1) -> q1

    You're not sending anything to own q0
    b to q1. But not is to q0 ?
    a to q2. But not is a to q1 ?
    The node labels are arbitrary. I just chose what seemed a logical numbering since my Moore machine has 6 states. I consider the two machines equivalent because: (1) for any input, the output of one machine is identical to that of the other machine, and (2) an input string is accepted in one machine if and only if it is accepted in the other machine.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Super Member
    Joined
    Jun 2008
    Posts
    829
    I think I understand. But in on your diagram has <q1|b> would not be <q1|0> ??
    Last edited by Apprentice123; June 26th 2010 at 06:34 PM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    MHF Contributor undefined's Avatar
    Joined
    Mar 2010
    From
    Chicago
    Posts
    2,340
    Awards
    1
    Quote Originally Posted by Apprentice123 View Post
    I think I understand. More in on your diagram has <q1|b> would not be <q1|0> ??
    I don't know what your question is. Could you explain? In my Moore diagram, the node q1 outputs a 0.
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Super Member
    Joined
    Jun 2008
    Posts
    829
    You make (q1|b).
    The correct not is (q1|0) ???

    () is the circle that represents the state
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Similar Math Help Forum Discussions

  1. Questions in Moore space
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: January 23rd 2011, 10:16 PM
  2. The Moore Metrization Theorem
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: July 28th 2010, 12:02 AM
  3. stability of moore space
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: June 30th 2010, 02:07 AM
  4. Mealy and Moore doubt
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: June 27th 2010, 07:02 AM
  5. references in metrization of moore space
    Posted in the Differential Geometry Forum
    Replies: 2
    Last Post: June 8th 2010, 09:44 PM

Search Tags


/mathhelpforum @mathhelpforum