A Moore machine is a type of finite state automaton (FSA) that is characterized by its output function. Unlike a Mealy machine, which produces output only when transitioning between states, a Moore machine produces output for each state and input symbol combination.
This means that a Moore machine can be used to generate output strings as well as recognize input strings.
In this type of machine, the future state of the machine is decided by the current state and current input symbol of the machine.
The output symbol at a given time depends only on the present state of the machine.
Moore machine is defined as a 6 tuple (Q, Σ, ∆, δ, λ, q0).
where,
- Q: A finite set of states.
- Σ: A finite set of input symbols.
- δ: A transition function: δ: Q x Σ → Q.
- λ: An output function: λ: Q x Σ → O.
- q₀: The start state.
- F: A set of accepting states.
Example Moore machine:
In Moore machine, each state has a fixed output, i.e. in above diagram,
- When machine is in state q1, the output is 0.
- When machine is in state q2, the output is 0.
- When machine is in state q3, the output is 1.
Referencees:
- Introduction to the Theory of Computation” by Michael Sipser.