Mealy Machine

A Mealy machine is a machine in which output symbol depends upon the present input symbol and present state of the machine. In the Mealy machine, the output is represented with each input symbol for each state separated by /.


The Mealy machine can be described by 6 tuples (Q, q0, ∑, O, δ, λ') where

Q:  a finite set of states  

q0: the initial state of the machine  

∑:   a finite set of the input alphabet  

O:   output alphabet  

δ:   transition function where Q × ∑ → Q  

λ:   output function where Q × ∑ →O 


//  If the input has n symbol, the output will contain n+1 symbol 



Example 1: Design a mealy machine that scans sequence of input of 0 and 1 and generates output 'A' if the input string terminates in 00, output 'B' if the string terminates in 11, and output 'C' otherwise.


Example 2: Draw a mealy machine for 2's complement.


The logic to construct a Mealy machine for 2's complement is:

Start scanning symbol from the right side and long as you see 0 leave it as 0 but when you see first 1 leave it as 1 and after that write down the  1's complement of every symbol you see.

for example: 2's complement for 1100101100 is 0011010100