A Moore machine and a Mealy machine both implement the same input-output function. Which of the following statements is most likely true about their sizes?
AThe Moore machine has fewer states because outputs are stored compactly in states rather than on every transition
BThe Mealy machine may have fewer states because output differentiation is handled by transition labels rather than requiring separate states
CBoth machines must have exactly the same number of states since they compute the same function
DThe Mealy machine always has more states because each transition must carry an output symbol
In a Moore machine, different outputs require different states — if two transitions into the same state would need to produce different outputs, you must split that state into two. In a Mealy machine, the same state can have different outputs on different outgoing transitions, avoiding the split. This means Mealy machines can often represent the same behavior with fewer states. The equivalence is in computational power, not in machine size.
Question 2 Multiple Choice
A traffic light controller cycles through RED, YELLOW, and GREEN based on a timer. Two designers disagree: one uses a Moore machine, the other a Mealy machine. A student claims the Moore machine is wrong because 'output should depend on the input.' What is wrong with this claim?
AThe student is correct — traffic lights must respond to sensor input, so only Mealy machines are appropriate
BThe student is wrong — both models are valid; in the Moore machine, the output (light color) depends only on which phase (state) the controller is in, not on the timer input that triggered the transition
CThe student is correct because Moore machines cannot produce multiple distinct output values
DThe student is wrong because Moore machines are more powerful than Mealy machines and can handle this case more efficiently
Both Moore and Mealy machines can model the traffic light. In the Moore model, the light color is a property of the current state (e.g., the 'RED phase' state always outputs RED), which is perfectly natural when output represents the stable condition of a phase. In the Mealy model, the output is on the transition (e.g., when the timer fires in RED state, output GREEN). Neither is wrong — they are equivalent in power. The student confuses 'output depends on input' (Mealy's definition) with 'output must depend on input' (a false requirement).
Question 3 True / False
A Mealy machine is strictly more powerful than a Moore machine — it can recognize languages or compute functions that a Moore machine cannot, because its output depends on both state and input.
TTrue
FFalse
Answer: False
Mealy and Moore machines are equivalent in computational power. Every Mealy machine can be converted to a Moore machine that computes the same input-output function, and vice versa. The difference is where output is associated (transitions vs states), which affects machine size and output timing — but not what functions can be computed. Both are transducers that map finite input sequences to finite output sequences.
Question 4 True / False
In a Moore machine, the same state always produces the same output regardless of which input symbol or transition sequence led to that state.
TTrue
FFalse
Answer: True
This is definitional: in a Moore machine, output is a function of the current state alone — output = f(state). No matter which path through the automaton led to state q, being in q always produces the same output. This is the fundamental contrast with Mealy machines, where output = g(state, input), so the same state can produce different outputs depending on which input is currently being read.
Question 5 Short Answer
Explain why a designer might prefer a Mealy machine over a Moore machine when implementing the same behavior, and give an example of when the Moore machine would require more states.
Think about your answer, then reveal below.
Model answer: A Mealy machine can encode output differentiation in transition labels, so a single state can produce different outputs on different transitions leaving it. A Moore machine must use separate states to produce different outputs, even if those states are otherwise identical in their transition behavior. For example, if a machine must output 0 or 1 depending on whether the current input is A or B, while staying in the same logical 'phase,' a Mealy machine handles this with one state and two labeled transitions; a Moore machine needs two states (one outputting 0, one outputting 1) with identical outgoing transitions.
The key insight is that Mealy machines pack more information into transitions, while Moore machines pack it into states. This is a design trade-off: Moore machines are often simpler to reason about (output is stable within a state), while Mealy machines are often more compact (fewer states needed when output varies within a phase).