Theory Of Computation

Section A

Moore and Mealy Machines

Mealy Machine

A Mealy Machine is an FSM whose output depends on the present state as well as the present input.

It can be described by a 6 tuple (Q, ∑, O, δ, X, q0) where −

• Q is a finite set of states.
• ∑ is a finite set of symbols called the input alphabet.
• O is a finite set of symbols called the output alphabet.
• δ is the input transition function where δ: Q × Σ→Q
• X is the output transition function where X: Q × Σ→O
• q0 is the initial state from where any input is processed (q0∈Q).

The state table of a Mealy Machine is shown below–

The state diagram of the above Mealy Machine is: