Finite state machines are composed of a finite number of states. These machines respond to some input by changing from one state to another. This change of state is also called transition.
Moore and Mealy machines are called Finite Automata with output. This is different from a DFAor NFA (Finite Automata without output) where there is no output (input is either accepted or rejected).
In a mealy machine, the output depends on the present state as well as the present input symbol. Here, the output is fixed for every transition (instead of state).
The mealy machine is also defined by 6-tuples (Q, Σ, Δ, δ, λ, q0):
Q = finite set of states
Σ = Input symbol
δ = Transition Function (Q x Σ -> Q)
q0 = Start state
Δ = Output Symbol
λ = Output function (Σ x Q -> Δ)
Example:
Consider the following mealy machine:
The transition table for the above mealy machine will be:
Current State
New State
0
1
State
Output
State
Output
A
B
a
A
b
B
A
b
B
a
The output for the string “1010” in the above machine will be:
States: A -> A -> B -> B -> A
Output: b a a b
Note that for an input string of length N, the output string will also have length N.
A Mealy machine is a type of finite state machine (FSM) used in automata theory and digital electronics. It is characterized by its output being dependent not only on the current state of the machine but also on the input. Here are some features and characteristics of Mealy machines:
State Transitions: Like any finite state machine, a Mealy machine consists of a finite number of states. It transitions between these states based on input signals.
Inputs: Mealy machines accept inputs from a specified input alphabet. These inputs trigger state transitions and affect the output generation.
Outputs: Unlike Moore machines, where outputs depend solely on the current state, in a Mealy machine, outputs are associated with transitions between states and inputs. The output is produced based on both the current state and the input received.
Output Function: The output function of a Mealy machine is defined as a mapping from the set of all possible state-input pairs to the set of output symbols.
Output Dependency: In a Mealy machine, the output is typically a function of the current state and the input signal that caused the transition to that state. Therefore, the output can change during state transitions triggered by different input symbols.
What is Moore Machine?
A Moore machine is an FSM (Finite State Machine) whose output depends on the present state. It is defined by 6-tuples (Q, Σ, Δ, δ, λ, q0):
Q = finite set of states
Σ = Input symbol
δ = Transition Function (Q x Σ -> Q)
q0 = Start state
Δ = Output Symbol
λ = Output function (Q -> Δ)
The output of a Moore machine in response to the input string a1 a2 a3 a4 ... aN is λ(q0) λ(q1) λ(q2) … λ(qN) where q0 q1 q2 is the sequence of states such that δ(qi-1, ai) = qi
Example:
Consider the following Moore machine
The transition table for the above machine will look like this:
Current State
Next State
Output
0
1
A
B
A
a
B
B
A
b
The output for the string “1010” in the above machine will be:
States: A -> A -> B -> A -> B
Output: a a b a b
Note that for a string of length N, the output string will have length N+1.
Features of Moore Machine
A Moore machine is another type of finite state machine used in automata theory and digital electronics. Unlike the Mealy machine, the output of a Moore machine depends only on the current state and not on the input. Here are some features and characteristics of Moore machines:
State Transitions: Similar to other finite state machines, a Moore machine consists of a finite number of states. It transitions between these states based on input signals.
Inputs: Moore machines accept inputs from a specified input alphabet. Inputs trigger state transitions, but they do not directly affect the output generation.
Outputs: In a Moore machine, outputs are associated solely with states and are independent of the input signals. The output is produced based only on the current state of the machine.
Output Function: The output function of a Moore machine is defined as a mapping from the set of all possible states to the set of output symbols. Each state is associated with a specific output symbol.
Output Dependency: In a Moore machine, the output is determined solely by the current state of the machine. Therefore, the output remains constant during state transitions triggered by different input symbols.Differences b/w Mealy and Moore machines
Differences b/w Mealy and Moore machines
Mealy Machine
Moore Machine
The output depends both on the present state and the present input.
The output depends only on the present state.
It generally has fewer states than Moore's machine.
Generally, a Moore machine has more states.
The hardware requirement is comparatively more for circuit implementation.
Less hardware requirement for circuit implementation.
They react faster to input.
Moore machines react slower to input.
The output generation is asynchronous.
The output and state of the change of the device are synchronous with the clock edge.
Comparatively difficult to design.
The output and state of the change of the device are synchronous with the clock edge.
Similarities b/w Moore and Mealy machines
Both Moore and Mealy machines do not have any final state.
We will use the following steps to convert the Moore machine, to a Mealy machine:-
Remove the output column: The output of a Mealy machine depends on the transition, thus the output column has to be removed.
Add output to transitions: The output of a transition is same as the output of the resultant state in Moore form. In the given table, output of state A is a, so, in the Mealy table, whenever the resultant state is A, the output will be a. Create a new column next to the resultant state, and add the output values.
Current State
0
1
State
Output
State
Output
A
B
b
A
a
B
A
a
B
b
The number of states in a Mealy machine is either smaller than, or equal to the number of states in an equivalent Moore machine.
In the next section you will learn how to convert a Mealy machine to a Moore machine.
We will use the following steps to convert the Mealy machine above, to a Moore machine:-
First, find the states that have more than 1 output associated with them. In the given table, B is associated with both a and b output, thus 2 new states Ba and Bb have to be created, similarly, C is associated with a and b as well, so, states Ca and Cb have to be created in the Moore equivalent transition table.
Creating output column: The output of a Moore machine depends on the current state, so it has to be evaluated from the transitions of the Mealy machine. For example, if the state changes from A to B and the output is c, the output of B in Moore machine will be c.
Current State
a
b
Output
Next State
Next State
A
Ba
A
a
Ba
Ba
Cb
a
Bb
Ba
Cb
b
Cb
Bb
Ca
b
Ca
Bb
Ca
a
If a Mealy machine has ‘m’ states and ‘n’ outputs, then the total number of states in Mealy machine, in a worst case condition will be m*n.
In the next section you will learn about the differences between Moore and Mealy machines.
Frequently Asked Questions
Who invented the Moore machine?
Edward F. Moore invented the Moore machine, a type of finite state machine, in 1956, advancing automata theory.
What is the use of Moore machine?
A Moore machine helps control things by following precise instructions, like traffic lights changing colors predictably to manage traffic flow.
What is DFA and NFA?
DFA (Deterministic Finite Automaton) and NFA (Nondeterministic Finite Automaton) are models in computer science to recognize patterns or languages.
Is DFA a Moore machine?
No, DFA (Deterministic Finite Automaton) is not a Moore machine. DFA has no output associated with its states, while Moore machines do.
What is Moore machine output?
A Moore machine's output is what it displays or produces as a response to an input, like a message or signal.
Where is Mealy machine used?
Mealy machines are used in electronics and computing to make decisions based on input signals and control various devices.
Which machine has 6 tuples?
Both Moore and Mealy machines are defined by 6 tuples. The 6 tuples are, finite set of states, input symbol, transition function, start state, output symbol, output function.
What is a practical example of a Moore machine?
A very simple example of a Moore machine is a doorbell, it has 2 states, idle and ringing. The output only depends on the current state.
Where are Moore machines used?
Moore machines are used for various application such as sequential logic design, implementation of communication protocols, design of embedded systems, industrial automation systems, traffic light control, etc.
Conclusion
In this article, we learned how to convert a DFA into an equivalent DFA having the minimum number of states. If you want to learn more about such topics, you can visit Coding Ninjas Studio.