Thread: 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?

Originally Posted by Apprentice123

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.

What have you done to find Moore diagram ? Which step in turning Mealy in Moore ?

Originally Posted by Apprentice123

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.

First you find a language that Mealy generates? What is the language that the Mealy diagram generated ?

Originally Posted by Apprentice123

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.

All entries are a or b and all outputs 1 or 0?


I can do:

Originally Posted by Apprentice123

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?

What I do not get it in your diagram is that it has alpha in q0. what the alpha ?

Originally Posted by Apprentice123

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.

Originally Posted by undefined

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 ?

Originally Posted by Apprentice123

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.

I think I understand. But in on your diagram has <q1|b> would not be <q1|0> ??

Originally Posted by Apprentice123

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.

You make (q1|b).
The correct not is (q1|0) ???

() is the circle that represents the state