​ ​ BS-CYBER SECURITY

Theory of Automata
BS (CYBER SECURITY)
PROJECT REPORT
MELAY AND MOORE MACHINES AND THEIR CONVERSIONS

Group Members: Dawood Shaikh & Huzaifa Mateen

Roll Numbers:​ BCB-23F-049 & BCB-23F-044

Section:​ ​ ​ CYB5

Department:​ ​ COMP. SCIENCE - CYBER​

Semester:​ ​ 5th

Submitted to:​​ Sir Irfan Leghari

Submitted on:​ 01-10-2026

Theory of Automata Page 1

 ​ ​ BS-CYBER SECURITY

Table of Contents
1.​Introduction

2.​Usability Method

3.​Conclusion

4.​References

Introduction
Finite-state machines (FSMs) are fundamental computational models used to represent systems
with a finite number of states and transitions between them. An FSM is defined by a set of
states (including a start state), an input alphabet, and transitions that specify how the machine
moves from one state to another in response to inputs. These machines are widely used in
theoretical computer science and engineering: for example, devices like vending machines,
elevators, and traffic lights can all be modeled as state machines. In automata theory, FSMs
include transducers (output-generating machines) such as Mealy and Moore machines, which
extend the basic FSM by producing outputs.
A Mealy machine is a type of finite-state transducer whose outputs depend on both the current
( )
state and the current input symbol. Formally, a Mealy machine is a 6-tuple 𝑞0 where 𝑄is a
finite set of states, Σthe input alphabet, 𝑂the output alphabet, δ: 𝑄×Σ→𝑄the transition
function, and λ: 𝑄×Σ→𝑂the output function. At each step, the Mealy machine reads an input
symbol, transitions to a new state according to δ, and simultaneously produces an output via
λ(𝑞, 𝑎). Because outputs are attached to transitions, Mealy machines can react to inputs quickly
– often producing an output in the same cycle the input arrives.
In contrast, a Moore machine is a finite-state transducer whose outputs depend only on the
current state. A Moore machine has a similar 6-tuple definition, but its output function λ: 𝑄→𝑂
maps states to output symbols, independent of the incoming input. In practice, this means the
output is emitted when entering a state (usually at the next clock tick) and is determined solely
by that state’s identity. Consequently, Moore outputs change one step later than the inputs (i.e.

Theory of Automata Page 2

 ​ ​ BS-CYBER SECURITY

on the next clock edge). Moore machines often have more states than an equivalent Mealy
machine, since each distinct output behavior typically requires a separate state.
Despite these differences, Mealy and Moore machines are equivalent in expressive power: for
any Mealy machine, there exists a Moore machine that produces the same output sequence (up
to a possible initial offset), and vice versa. In digital system design and automata theory, the
choice between Mealy and Moore representations depends on trade-offs. Mealy machines can
require fewer states and can respond faster to inputs, but their outputs can glitch when inputs
change mid-cycle. Moore machines produce stable outputs synchronized to clock edges, which
can simplify hardware implementation, albeit with extra states and a one-cycle delay.
Understanding Mealy vs. Moore machines is crucial in automata theory and practical system
design. For example, a hardware designer might prefer a Moore design to avoid race conditions,
while a compiler’s lexer might use a Mealy-like state machine for efficiency. Converting between
these forms is therefore a key skill. The next sections focus on the specific method to transform
a given Mealy machine into an equivalent Moore machine: we outline the algorithmic steps,
discuss behavioral effects (such as output delay and state duplication), and illustrate with
example state diagrams.

Usability Method
To convert a Mealy machine into a Moore machine, we systematically reassign outputs from
transitions to states. The high-level idea is to ensure that each Moore-state emits the correct
output when entered, matching the Mealy machine’s behavior except possibly delayed by one
input cycle. The algorithm proceeds roughly as follows:
1.​ Identify states with multiple outputs: For each Mealy state 𝑞, examine all outgoing (or
incoming) transitions and note the outputs produced on each. If state 𝑞has more than
one distinct output symbol associated with transitions, it must be split in the Moore
machine. That is, we will create separate Moore states for 𝑞corresponding to each
distinct output..
2.​ Split each multi-output state: Create new Moore states 𝑞0, 𝑞1, …for each Mealy state 𝑞
that had multiple outputs. Label each new state 𝑞𝑥with one of the output values from 𝑞.
For example, if 𝑞had outputs 0 and 1 on different transitions, make states 𝑞0(output 0)
and 𝑞1(output 1). If a state already had a single output on all its transitions, we can use a
single copy for it. This step mirrors the instruction “for each state, break it into 𝑛states if
it has 𝑛distinct outputs”

Theory of Automata Page 3

 ​ ​ BS-CYBER SECURITY

3.​ Redirect transitions: Construct the Moore transition function based on the Mealy
𝑎/𝑦
transitions. Every Mealy transition 𝑝→ 𝑟(from state 𝑝on input 𝑎, output 𝑦, to state 𝑟)
now becomes a Moore transition from state 𝑝𝑥to state 𝑟𝑦on input 𝑎, where 𝑝𝑥is the copy
of 𝑝labeled with the output on that transition, and 𝑟𝑦is the copy of 𝑟labeled with the
output that 𝑟would produce on its incoming transition. In effect, the input labels on
transitions remain the same, but the output label is now carried by the target state
instead of the edge.
4.​ Set Moore outputs: In the Moore machine, assign each new state 𝑞𝑜the output 𝑜that it
was labeled with. Thus the output function λ𝑀𝑜𝑜𝑟𝑒(𝑞𝑜) = 𝑜, independent of input. All
transition arrows are then simply labeled with the input symbol (no output).
5.​ Handle the initial state/output: Because a Moore machine must produce an output at
the very first step (initial state output) before reading any inputs, we must assign an
initial output. If the original Mealy machine would produce some output on its first
input, the Moore machine’s initial state should output a dummy symbol (e.g.
“no-output”) or we designate one of the new states as initial with an output that causes
the correct first output upon the first transition. In many constructions, the Moore
machine’s output sequence will match the Mealy’s output sequence delayed by one
input.
These steps effectively “move” the Mealy outputs into the state labels of the Moore machine. In
particular, any Mealy state with multiple output behaviors is duplicated in the Moore version so
that each copy has a single fixed output. For example, if a Mealy state 𝑞has transitions that
produce 0 and others that produce 1, we create two Moore states 𝑞0and 𝑞1to capture these
cases separately.
Example Illustration: Consider the simple Mealy machine shown in Figure 1. In this machine,
each transition is labeled with an input/output pair of the form input/output. The machine
consists of three states: q0, q1, and q2. The output produced by the machine depends on both
the current state and the input symbol (0 or 1), which is the defining characteristic of a Mealy
machine.

Theory of Automata Page 4

 ​ ​ BS-CYBER SECURITY

In Figure 1, state q0 produces output 0 on both input 0 and input 1, transitioning to states q1
and q2, respectively. However, states q1 and q2 each produce different outputs depending on
the input. For example, state q1 produces output 0 on input 0 and output 1 on input 1, while
state q2 produces output 1 on input 0 and output 0 on input 1. This means that states q1 and q2
exhibit multiple output behaviors, which necessitates state splitting during conversion to a
Moore machine.
Figure 1: Mealy machine state diagram in which outputs (0 or 1) are associated with transitions.
Each transition is labeled with an input/output pair.
To convert this Mealy machine into a Moore machine, we apply the standard Mealy-to-Moore
conversion procedure. Since a Moore machine requires that each state produce exactly one
fixed output, any Mealy state that produces more than one output must be split into multiple
states—one for each distinct output.
Applying this procedure, state q1 is split into q1/0 and q1/1, representing the cases where the
output is 0 and 1, respectively. Similarly, state q2 is split into q2/0 and q2/1. State q0, which
produces only output 0, does not require splitting. Transitions are then redirected so that each
transition leads to the appropriate state corresponding to the output produced in the original
Mealy machine. The resulting Moore machine is shown in Figure 2.

Theory of Automata Page 5

 ​ ​ BS-CYBER SECURITY

Figure 2: Equivalent Moore machine obtained from the Mealy machine in Figure 1. Each state is
labeled with a single output value (written inside the state), and transitions are labeled only
with input symbols.
In the Moore machine, outputs are generated only when a state is entered, and therefore are
independent of the current input. As a result, the output sequence produced by the Moore
machine is functionally equivalent to that of the original Mealy machine but is delayed by one
input step. If the Mealy machine produces outputs 𝑦1, 𝑦2, …in response to inputs 𝑎1, 𝑎2, …, the
Moore machine will typically produce an initial output (often a default or null value) and then
output 𝑦1, 𝑦2, …on subsequent transitions. This one-step delay arises because Moore machines
emit outputs upon entering a state, rather than during the transition itself.
Behavioral Considerations: The Mealy-to-Moore conversion has important side effects. First, as
noted, the Moore machine’s outputs occur one cycle later: Moore’s outputs change only on
state transitions (often synchronized to a clock edge), whereas a Mealy machine could change
its output immediately when the input changes. This means any timing-sensitive design must
account for the extra latency. Second, the conversion generally increases the number of states.
Each Mealy state with 𝑛distinct output behaviors becomes 𝑛separate Moore states. In the worst
case, the Moore machine can have as many states as the number of Mealy transitions, since
every transition output could force a separate state. In practice, if many states only ever

Theory of Automata Page 6

 ​ ​ BS-CYBER SECURITY

produce one output, the blow-up is moderate, but if many states had diverse output values, the
Moore machine “explodes” in size. Finally, we must choose an initial output for the Moore
machine: often this is a designated “no output” symbol or the output of one of the split
initial-state copies.
In summary, converting a Mealy machine into a Moore machine involves creating duplicate
states to separate output behaviors and reassigning outputs from edges into states. The
resulting Moore machine is functionally equivalent (modulo the first-step delay) but may have a
higher state count. Figure 2 exemplifies the final result of this procedure for our sample Mealy
machine.

Conclusion
Mealy and Moore machines are two equivalent formalisms for modeling sequential systems,
differing only in how outputs are associated with states or transitions. In a Mealy machine,
outputs depend on the current state and input, yielding faster reactions but potentially more
complex logic and timing sensitivity. In a Moore machine, outputs depend solely on the current
state, which simplifies output logic and ensures outputs are only updated on state changes
(usually at clock edges). The standard conversion from Mealy to Moore moves output logic into
the state labels, creating extra states as needed so that each state has a single output value.
The insights from this conversion are broadly useful. For example, designing a sequence
detector (a common digital circuit) often leads to a choice between Mealy and Moore
implementations. A Mealy detector may use fewer states and detect patterns immediately as
inputs arrive, whereas a Moore detector provides cleaner output timing by waiting until a state
is fully entered. In many practical controllers or digital designs, Moore machines are preferred
for their stability; yet Mealy machines can yield more compact circuits. By understanding the
conversion process, designers and theoreticians know that they can trade one form for the
other: a Mealy design can be turned into an equivalent Moore design if synchronous outputs
are required, and vice versa.
In this report we have detailed the conversion algorithm: identify states with multiple output
behaviors, duplicate them as needed, and rewire transitions so that each new Moore state
carries the correct output. We emphasized the behavioral considerations: notably, the Moore
machine’s outputs will be one step delayed compared to the Mealy machine, and the state
complexity generally increases. These factors illustrate the trade-offs in using each model.
Overall, both Mealy and Moore machines remain fundamental tools in automata theory and
digital system design, and mastering their interconversion is valuable for theoretical
understanding and practical implementation.

Theory of Automata Page 7

 ​ ​ BS-CYBER SECURITY

References
●​ Wikipedia contributors, “Finite-state machine,” Wikipedia, The Free Encyclopedia
(2025)[Link].
●​ Wikipedia contributors, “Mealy machine,” Wikipedia, The Free Encyclopedia
(2025)[Link].
●​ Xilinx Inc., UG958 (Vivado Design Suite User Guide): Moore State Machine,
[Link].
●​ GeeksforGeeks, “Mealy and Moore Machines in Theory of Computation,” (updated 23 Jul
2025)[Link].
●​ DCTLib (StackExchange user), “How to convert such Mealy machines into single initial
state Moore machines?”, Computer Science StackExchange, March
[Link].
●​ SiliconCrafters, “A primer on Mealy and Moore Finite State Machines,” SiliconCrafters
Blog, Apr. 9, [Link].

Theory of Automata Page 8