How to understand the Mealy and Moore machine

How to understand the Mealy machine

A mealy machine is a tuple M = (E, S, A, d, g, s0) with

E = {e1, â€¦, er} : input alphabet

S = {s0, â€¦, sn} : set of states

A = {a1, â€¦, am} : output alphabet

d : S x E â†’ S : transition function

g : S x E â†’ A : output function

s0 : start state

If you are in the beginnings of studying theory of computation, like me and you just don't understand what this tuple M is all about and what all these symbols mean, then hopefully this article will give you some easy examples to understand the Mealy and Moore machine. Maybe you already looked up the Mealy machine on Wikipedia and noticed that there is only a formal definition of it and no easy to understand explanation and examples. I am going to answer common questions that beginners lie me face when trying to study for the next theory of computation exam while learning and trying to understand the Mealy machine.

What is this tupel M?

A tupel is an ordered list of elements. In our case of the Mealy machine it consists the elements that a Mealy machine needs in order to work. You need an alphabet for input. For example E = {0, 1} means you are only allowed to enter 0s and 1s. So, a Mealy machine with E = {0, 1} does not accept an "a" or a "2" or "@" as an input. Even not "01" as this is a word of length two. If you have an input alphabet with E = {00, 01, 10, 11} then the input "01" is accepted. Do you now understand the concept a little bit? Let's continue with the set of states "S = {s0, â€¦, sn}". In the set of states you find elements that define a state. The initial state or start sate is s0. It is contained in the list of states. That is where the Mealy machine starts from before even entering an input.

Now if you give this machine in the picture the input "1", it will give you the output "0" because we are starting from the initial state s0. After giving the output the Mealy machine goes into the state s1 according the function d : S x E â†’ S. This complicated formula basically means that you have a state "S" (e.g. s0) and you combine it with an Input "E" (e.g. "!") then the Mealy machine will be in state "S" (e.g. s1). The output function g : S x E â†’ A defines the output "A" that the Mealy machine gives you when you enter an input "E" in a state "S". An important fact to remember is that the Mealy machine gives you the output as soon as you enter the input. Notice how the output is written next to the input on the arrow? So you basically receive the output BEFORE you enter the next state. This is an important property to remember! Since the Moore machine works exactly the same you can save a lot of time when you want to understand the Mealy and Moore machines with little effort. The Moore machine gives you the output when reaching a new state, not BEFORE. This technically means, you give an input; the Moore machine goes into a new state and after reaching this new state, it THEN pops out the output of that state.

Let's understand the Moore machine together.

How to understand the Moore machine

A Moore machine is a tuple M = (E, S, A, d, g, s0) with

E = {e1, â€¦, er} : input alphabet

S = {s0, â€¦, sn} : set of states

A = {a1, â€¦, am} : output alphabet

d : S x E â†’ S : transition function

g : S â†’ A : output function

s0 : start state

If you want to understand the difference between Mealy and Moore machine, you need to take a very close look at the output function g : S â†’ A. Maybe you see the difference between Mealy and Moore, if I write like this: Mealy's output function g : S x Eâ†’ A and Moore's output function g : S â†’ A.

The output function of Moore returns an output when it is in a given state "S" (for example: s1). To understand the Mealy and Moore machines, let's look at a picture.

As you see, the output is related to a state. E.g. being in state "10" means that the Moore machine returns a "11". If you now enter "x=1" the Moore machine will go from "10" to sate "00". Reaching state "00" will give you the output "01".

Another important fact to know, when you want to understand the Mealy and the Moore machine: To every Mealy machine you can construct an equivalent Moore machine and vice versa.

The amounts of states may vary greatly even though the difference between Mealy and Moore might just the output function!

Did you understand the Mealy and Moore machine and the difference between the two? If not, post your question in the comments.