My Moore and Mealy machines look the same. Why?
$begingroup$
For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with different labels.
Example
Input alphabet: {0, 1, ..., 9}
Output alphabet: {0, 1}
Function: Output 1 if the current number is divisible by 3, else output 0.
Moore
Mealy
You see, all I did for creating the Mealy machine was moving the output from the nodes to the connections. Which would make it quite trivial to convert an arbitary Moore machine to a Mealy machine.
Possible sources of my confusion:
- My understanding of the differences between the two types is fundamentally flawed.
- The conversion Moore => Mealy is in fact trivial.
- This example is a special case where the Mealy and Moore machines look the same.
- There is a simpler Mealy machine than the one I built here.
- My Moore machine is not a valid Moore machine. / My Mealy machine is not a valid Mealy machine. (see 4)
I tried to start from scratch building the Mealy machine, but as I found Moore much easier to build I am always biased towards the Moore solution.
automata
$endgroup$
|
show 4 more comments
$begingroup$
For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with different labels.
Example
Input alphabet: {0, 1, ..., 9}
Output alphabet: {0, 1}
Function: Output 1 if the current number is divisible by 3, else output 0.
Moore
Mealy
You see, all I did for creating the Mealy machine was moving the output from the nodes to the connections. Which would make it quite trivial to convert an arbitary Moore machine to a Mealy machine.
Possible sources of my confusion:
- My understanding of the differences between the two types is fundamentally flawed.
- The conversion Moore => Mealy is in fact trivial.
- This example is a special case where the Mealy and Moore machines look the same.
- There is a simpler Mealy machine than the one I built here.
- My Moore machine is not a valid Moore machine. / My Mealy machine is not a valid Mealy machine. (see 4)
I tried to start from scratch building the Mealy machine, but as I found Moore much easier to build I am always biased towards the Moore solution.
automata
$endgroup$
1
$begingroup$
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states.
$endgroup$
– copper.hat
Jan 2 '13 at 0:09
1
$begingroup$
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams.
$endgroup$
– Lucius
Jan 2 '13 at 0:10
$begingroup$
Or maybe your professor intended for you to have this realisation!
$endgroup$
– Alex J Best
Jan 2 '13 at 0:26
1
$begingroup$
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times ${2,4,7}$ is seen less the number of times ${1,4,7 }$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum.
$endgroup$
– copper.hat
Jan 2 '13 at 0:32
1
$begingroup$
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point.
$endgroup$
– Lucius
Jan 2 '13 at 0:44
|
show 4 more comments
$begingroup$
For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with different labels.
Example
Input alphabet: {0, 1, ..., 9}
Output alphabet: {0, 1}
Function: Output 1 if the current number is divisible by 3, else output 0.
Moore
Mealy
You see, all I did for creating the Mealy machine was moving the output from the nodes to the connections. Which would make it quite trivial to convert an arbitary Moore machine to a Mealy machine.
Possible sources of my confusion:
- My understanding of the differences between the two types is fundamentally flawed.
- The conversion Moore => Mealy is in fact trivial.
- This example is a special case where the Mealy and Moore machines look the same.
- There is a simpler Mealy machine than the one I built here.
- My Moore machine is not a valid Moore machine. / My Mealy machine is not a valid Mealy machine. (see 4)
I tried to start from scratch building the Mealy machine, but as I found Moore much easier to build I am always biased towards the Moore solution.
automata
$endgroup$
For university I have to construct equivalent Mealy and Moore machines that solve certain problems. But I am confused, as my Moore and Mealy machines turn out to have exactly the same nodes, just with different labels.
Example
Input alphabet: {0, 1, ..., 9}
Output alphabet: {0, 1}
Function: Output 1 if the current number is divisible by 3, else output 0.
Moore
Mealy
You see, all I did for creating the Mealy machine was moving the output from the nodes to the connections. Which would make it quite trivial to convert an arbitary Moore machine to a Mealy machine.
Possible sources of my confusion:
- My understanding of the differences between the two types is fundamentally flawed.
- The conversion Moore => Mealy is in fact trivial.
- This example is a special case where the Mealy and Moore machines look the same.
- There is a simpler Mealy machine than the one I built here.
- My Moore machine is not a valid Moore machine. / My Mealy machine is not a valid Mealy machine. (see 4)
I tried to start from scratch building the Mealy machine, but as I found Moore much easier to build I am always biased towards the Moore solution.
automata
automata
edited Jan 2 '13 at 0:13
Lucius
asked Jan 1 '13 at 23:58
LuciusLucius
1165
1165
1
$begingroup$
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states.
$endgroup$
– copper.hat
Jan 2 '13 at 0:09
1
$begingroup$
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams.
$endgroup$
– Lucius
Jan 2 '13 at 0:10
$begingroup$
Or maybe your professor intended for you to have this realisation!
$endgroup$
– Alex J Best
Jan 2 '13 at 0:26
1
$begingroup$
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times ${2,4,7}$ is seen less the number of times ${1,4,7 }$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum.
$endgroup$
– copper.hat
Jan 2 '13 at 0:32
1
$begingroup$
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point.
$endgroup$
– Lucius
Jan 2 '13 at 0:44
|
show 4 more comments
1
$begingroup$
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states.
$endgroup$
– copper.hat
Jan 2 '13 at 0:09
1
$begingroup$
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams.
$endgroup$
– Lucius
Jan 2 '13 at 0:10
$begingroup$
Or maybe your professor intended for you to have this realisation!
$endgroup$
– Alex J Best
Jan 2 '13 at 0:26
1
$begingroup$
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times ${2,4,7}$ is seen less the number of times ${1,4,7 }$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum.
$endgroup$
– copper.hat
Jan 2 '13 at 0:32
1
$begingroup$
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point.
$endgroup$
– Lucius
Jan 2 '13 at 0:44
1
1
$begingroup$
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states.
$endgroup$
– copper.hat
Jan 2 '13 at 0:09
$begingroup$
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states.
$endgroup$
– copper.hat
Jan 2 '13 at 0:09
1
1
$begingroup$
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams.
$endgroup$
– Lucius
Jan 2 '13 at 0:10
$begingroup$
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams.
$endgroup$
– Lucius
Jan 2 '13 at 0:10
$begingroup$
Or maybe your professor intended for you to have this realisation!
$endgroup$
– Alex J Best
Jan 2 '13 at 0:26
$begingroup$
Or maybe your professor intended for you to have this realisation!
$endgroup$
– Alex J Best
Jan 2 '13 at 0:26
1
1
$begingroup$
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times ${2,4,7}$ is seen less the number of times ${1,4,7 }$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum.
$endgroup$
– copper.hat
Jan 2 '13 at 0:32
$begingroup$
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times ${2,4,7}$ is seen less the number of times ${1,4,7 }$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum.
$endgroup$
– copper.hat
Jan 2 '13 at 0:32
1
1
$begingroup$
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point.
$endgroup$
– Lucius
Jan 2 '13 at 0:44
$begingroup$
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point.
$endgroup$
– Lucius
Jan 2 '13 at 0:44
|
show 4 more comments
1 Answer
1
active
oldest
votes
$begingroup$
The only difference between a Moore machine and a Mealy machine is how the output of the machine is defined. In a Moore machine, the output is based solely off the current state. In the formal definition, we say that there is an output function $$
G:Srightarrow Lambda
$$
where $S$ is the set of states and $Lambda$ is the output alphabet (i.e. the set of symbols that could possibly be output). So this function $G$ takes a state and outputs a symbol. In a Mealy machine, the output is based off of the current state and the current input. In the formal definition, we say that there is an output function $$
G:StimesSigmarightarrow Lambda
$$
where $S$ is the set of states, $Sigma$ is the input alphabet (i.e. the set of symbols that could possibly be input), and $Lambda$ is the output alphabet. So this function $G$ takes a pair, one state and one input symbol, and outputs a symbol.
We can see by this definition that a Moore machine is just a special type of Mealy machine such that the Mealy machine's input symbol is ignored in the output. If we wanted to turn a Moore machine into a Mealy machine, we would change our function $G_1:Srightarrow Lambda$ to a function $G_2:StimesSigmarightarrow Lambda$ so that for any input symbol $ain Sigma$ and state $sin S$, $$
G_2(s,a)=G_1(s)
$$
So Mealy machines have extra functionality that Moore machines don't have. Notice in your Mealy machine diagram, for any given state every arrow coming into the state has the same output. This means that we can very easily change the output to be a function of the state, rather than of the input.
In fact, any Moore machine can be converted to a Mealy machine and vice versa, but generally the minimal Mealy machine will have fewer states than the minimal Moore machine.
For any representation of a Mealy machine, one can convert to a Moore machine without the addition or relabeling of states only if for any state of the Mealy machine, every transition into the state has the same output.
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f268888%2fmy-moore-and-mealy-machines-look-the-same-why%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The only difference between a Moore machine and a Mealy machine is how the output of the machine is defined. In a Moore machine, the output is based solely off the current state. In the formal definition, we say that there is an output function $$
G:Srightarrow Lambda
$$
where $S$ is the set of states and $Lambda$ is the output alphabet (i.e. the set of symbols that could possibly be output). So this function $G$ takes a state and outputs a symbol. In a Mealy machine, the output is based off of the current state and the current input. In the formal definition, we say that there is an output function $$
G:StimesSigmarightarrow Lambda
$$
where $S$ is the set of states, $Sigma$ is the input alphabet (i.e. the set of symbols that could possibly be input), and $Lambda$ is the output alphabet. So this function $G$ takes a pair, one state and one input symbol, and outputs a symbol.
We can see by this definition that a Moore machine is just a special type of Mealy machine such that the Mealy machine's input symbol is ignored in the output. If we wanted to turn a Moore machine into a Mealy machine, we would change our function $G_1:Srightarrow Lambda$ to a function $G_2:StimesSigmarightarrow Lambda$ so that for any input symbol $ain Sigma$ and state $sin S$, $$
G_2(s,a)=G_1(s)
$$
So Mealy machines have extra functionality that Moore machines don't have. Notice in your Mealy machine diagram, for any given state every arrow coming into the state has the same output. This means that we can very easily change the output to be a function of the state, rather than of the input.
In fact, any Moore machine can be converted to a Mealy machine and vice versa, but generally the minimal Mealy machine will have fewer states than the minimal Moore machine.
For any representation of a Mealy machine, one can convert to a Moore machine without the addition or relabeling of states only if for any state of the Mealy machine, every transition into the state has the same output.
$endgroup$
add a comment |
$begingroup$
The only difference between a Moore machine and a Mealy machine is how the output of the machine is defined. In a Moore machine, the output is based solely off the current state. In the formal definition, we say that there is an output function $$
G:Srightarrow Lambda
$$
where $S$ is the set of states and $Lambda$ is the output alphabet (i.e. the set of symbols that could possibly be output). So this function $G$ takes a state and outputs a symbol. In a Mealy machine, the output is based off of the current state and the current input. In the formal definition, we say that there is an output function $$
G:StimesSigmarightarrow Lambda
$$
where $S$ is the set of states, $Sigma$ is the input alphabet (i.e. the set of symbols that could possibly be input), and $Lambda$ is the output alphabet. So this function $G$ takes a pair, one state and one input symbol, and outputs a symbol.
We can see by this definition that a Moore machine is just a special type of Mealy machine such that the Mealy machine's input symbol is ignored in the output. If we wanted to turn a Moore machine into a Mealy machine, we would change our function $G_1:Srightarrow Lambda$ to a function $G_2:StimesSigmarightarrow Lambda$ so that for any input symbol $ain Sigma$ and state $sin S$, $$
G_2(s,a)=G_1(s)
$$
So Mealy machines have extra functionality that Moore machines don't have. Notice in your Mealy machine diagram, for any given state every arrow coming into the state has the same output. This means that we can very easily change the output to be a function of the state, rather than of the input.
In fact, any Moore machine can be converted to a Mealy machine and vice versa, but generally the minimal Mealy machine will have fewer states than the minimal Moore machine.
For any representation of a Mealy machine, one can convert to a Moore machine without the addition or relabeling of states only if for any state of the Mealy machine, every transition into the state has the same output.
$endgroup$
add a comment |
$begingroup$
The only difference between a Moore machine and a Mealy machine is how the output of the machine is defined. In a Moore machine, the output is based solely off the current state. In the formal definition, we say that there is an output function $$
G:Srightarrow Lambda
$$
where $S$ is the set of states and $Lambda$ is the output alphabet (i.e. the set of symbols that could possibly be output). So this function $G$ takes a state and outputs a symbol. In a Mealy machine, the output is based off of the current state and the current input. In the formal definition, we say that there is an output function $$
G:StimesSigmarightarrow Lambda
$$
where $S$ is the set of states, $Sigma$ is the input alphabet (i.e. the set of symbols that could possibly be input), and $Lambda$ is the output alphabet. So this function $G$ takes a pair, one state and one input symbol, and outputs a symbol.
We can see by this definition that a Moore machine is just a special type of Mealy machine such that the Mealy machine's input symbol is ignored in the output. If we wanted to turn a Moore machine into a Mealy machine, we would change our function $G_1:Srightarrow Lambda$ to a function $G_2:StimesSigmarightarrow Lambda$ so that for any input symbol $ain Sigma$ and state $sin S$, $$
G_2(s,a)=G_1(s)
$$
So Mealy machines have extra functionality that Moore machines don't have. Notice in your Mealy machine diagram, for any given state every arrow coming into the state has the same output. This means that we can very easily change the output to be a function of the state, rather than of the input.
In fact, any Moore machine can be converted to a Mealy machine and vice versa, but generally the minimal Mealy machine will have fewer states than the minimal Moore machine.
For any representation of a Mealy machine, one can convert to a Moore machine without the addition or relabeling of states only if for any state of the Mealy machine, every transition into the state has the same output.
$endgroup$
The only difference between a Moore machine and a Mealy machine is how the output of the machine is defined. In a Moore machine, the output is based solely off the current state. In the formal definition, we say that there is an output function $$
G:Srightarrow Lambda
$$
where $S$ is the set of states and $Lambda$ is the output alphabet (i.e. the set of symbols that could possibly be output). So this function $G$ takes a state and outputs a symbol. In a Mealy machine, the output is based off of the current state and the current input. In the formal definition, we say that there is an output function $$
G:StimesSigmarightarrow Lambda
$$
where $S$ is the set of states, $Sigma$ is the input alphabet (i.e. the set of symbols that could possibly be input), and $Lambda$ is the output alphabet. So this function $G$ takes a pair, one state and one input symbol, and outputs a symbol.
We can see by this definition that a Moore machine is just a special type of Mealy machine such that the Mealy machine's input symbol is ignored in the output. If we wanted to turn a Moore machine into a Mealy machine, we would change our function $G_1:Srightarrow Lambda$ to a function $G_2:StimesSigmarightarrow Lambda$ so that for any input symbol $ain Sigma$ and state $sin S$, $$
G_2(s,a)=G_1(s)
$$
So Mealy machines have extra functionality that Moore machines don't have. Notice in your Mealy machine diagram, for any given state every arrow coming into the state has the same output. This means that we can very easily change the output to be a function of the state, rather than of the input.
In fact, any Moore machine can be converted to a Mealy machine and vice versa, but generally the minimal Mealy machine will have fewer states than the minimal Moore machine.
For any representation of a Mealy machine, one can convert to a Moore machine without the addition or relabeling of states only if for any state of the Mealy machine, every transition into the state has the same output.
answered Nov 12 '18 at 20:12
Joey KilpatrickJoey Kilpatrick
1,181422
1,181422
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f268888%2fmy-moore-and-mealy-machines-look-the-same-why%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
A Moore machine is (essentially, you need to add labels) a Mealy machine. The Moore outputs are a function of state (only), whereas the Mealy outputs may change with inputs. A Mealy machine can always be converted to a Moore machine, with the possible addition of extra states.
$endgroup$
– copper.hat
Jan 2 '13 at 0:09
1
$begingroup$
This renders the excercise of building a Moore and a Mealy machine for the same problem kind of pointless. Unless my professor only wants to test my ability to draw diagrams.
$endgroup$
– Lucius
Jan 2 '13 at 0:10
$begingroup$
Or maybe your professor intended for you to have this realisation!
$endgroup$
– Alex J Best
Jan 2 '13 at 0:26
1
$begingroup$
A brief glance at your machine suggests to me that you need a minimum of 3 states, so the above seems reasonable. It seems to be counting the number of times ${2,4,7}$ is seen less the number of times ${1,4,7 }$ is seen, and outputs $1$ iff the count is $0$ modulo $3$. Hence $3$ states are needed at minimum.
$endgroup$
– copper.hat
Jan 2 '13 at 0:32
1
$begingroup$
@Alex: There are two excerises that require me to build a Mealy and a Moore machine for the same problem. I wonder if my professor thought that it is necessary to have this realisation twice. Otherwise I still don't see the point.
$endgroup$
– Lucius
Jan 2 '13 at 0:44