Theory Of Computation

Section A

Mealy Machine to Moore Machine

Algorithm 5:

Input: Mealy Machine

Output: Moore Machine

Step 1 Calculate the number of different outputs for each state (Qi) that are     available in the state table of the Mealy machine.

Step2 If all the outputs of Q are same,copy state Qi.If it has n distinct outputs,break Qi into n states as Qin where n=0, 1,2.......

Step 3 If the output of the initial state is 1, insert a new initial state at the beginning which gives 0 output.

Example

Let us consider the following Mealy Machine:

Here, states ‘a’ and ‘d’ give only 1 and 0 outputs respectively,so we retain states ‘a’ and ‘d’. But states ‘b’ and ‘c’ produce different outputs (1 and 0).So, we divide b into b 0 ,b1 and c into c0,c1.