Mealy moore machine model

Mealy Moore and their conversions

1. Mealy & Moore Machine Models
08/20/14Er. Deepinder Kaur

2. Mealy Machine Model
08/20/14Er. Deepinder Kaur
In Mealy machine. the value of output function is depend
on the present state and present input. In mealy machine every transition
for a particular input symbol has a fixed output.
Mealy machine is described by 6-tuples - (Q, Σ, Δ, δ, λ, q
0
)
 
          where
          Q = Finite non-empty set of states;
          Σ = Set of input alphabets.
          Δ = Set of output alphabets.
          δ = Transitional function mapping Q X Σ → Q
          λ = Output function mapping Q X Σ → Δ
          q
0 =
 Initial state.

3. δ: it is transition function which takes two arguments as in finite automata, one is input
state and another input symbol
λ’: is a mapping function which maps Q x ∑ to

∆ giving the output associated with
each transition
q0: initial state
So λ’ maps Q x ∑

∆ that is λ’(q,a) gives the output associated with the transition
from state q0 on input a. The output of Me in response to input a1,a2,a3…..an is
λ’(q0,a1), λ’(q1,a2)………λ’(qn-1,an) where q0,q1,q2……….qn is the sequence
of states such that
δ(qi-1,ai)=qi for 1<=i<=n

4. Mealy Machine Model
08/20/14Er. Deepinder Kaur

Sample Transition table
Present State
Next State
a = 0 a = 1
State Output State Output
-> q0 q3 0 q1 1
q1 q0 1 q3 0
q2 q2 1 q2 0
q3 q1 0 q0 1
Where λ’(q0,0)=0, λ’(q0,1)=1, λ’(q1,0)=1 ,λ’(q1,1)=0, λ’(q2,0)=1
λ’(q2,1)=0
λ’(q3,0)=10, λ’(q3,1)=1

5. Moore Machine Model
08/20/14Er. Deepinder Kaur
In Moore machine. the value of output function is depend on
the present state only.
Moore machine is described by 6-tuples - (Q, Σ, Δ, δ, λ, q
0
)
          where
          Q = Finite non-empty set of states;
          Σ = Set of input alphabets.
          Δ = Set of output alphabets.
          δ = Transition function mapping Q X Σ → Q
          λ = Output function mapping Q → Δ
q
0 =
 Initial state..

6. δ: it is transition function which takes two arguments as in finite automata, one is input state
and another input symbol
λ’: is a mapping function which maps Q to

∆ giving the output associated with each state
q0: initial state
let Mo be a moore machine and ∑ is a1,a2,a3------an, then output of M0 for ∑ is λ’(q0),
λ’(q1), λ’(q2)………λ’(qn) where q0,q1,q2……….qn is the sequence of states such that
δ(qi-1,ai)=qi for 1<=i<=n
Moore machine can be represented by transition table as well as transition diagram same as
finite automata

7. Moore Machine Model
08/20/14Er. Deepinder Kaur
Sample Transition Table:
Present State
Next State
Output
a = 0 a = 1
-> q0 q3 q1 1
q1 q0 q3 0
q2 q2 q2 0
q3 q1 q0 1
Where λ’(q0)=1, λ’(q1)=0, λ’(q2)=0 and λ’(q3)=1. there is no
concept of final state in moore machineas we consider output for
each state.

8. Representation of Moore machine
Present state Next state
a=0
a=1
output
q0 q3 q10
q1 q1 q21
q2 q2 q30
q3 q3 q00

9. q0
0
1
1
0
0
1
0
0
1
1
0
0
q1
q2
q3
Output for every state is written just above the state
Present statePresent state

10. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur
Steps:
 
Step 1:
For a state q
i
determine the number of outputs that are available in θ state table
of the Mealy machine.
Step 2:
If the outputs corresponding to state q
i
in the next state columns are same,
then retain state q
i
as it is. Else, break q
i
into different states with the number of
new states being equal to the number of different outputs of q
i.
e.g. suppose in the next state column of the above sample
transition table of mealy machine, the output associated with q1
is "0" in the first next state column and
"1" in the second next state column.
so we split q1 into q10 and q11 states.
similarly check others and split them.

11. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur

Step 3:
Rearrange the states and outputs in the format of Moore machine.
The common output of the new state table can be determined by examining
the outputs under the next state columns of the Mealy machine.
Step 4:
If the output in the constructed state table corresponding to the initial state is 1,
then this specifies the acceptance of the null string ^ by Mealy machine.
Hence, to make both the Mealy and Moore machines equivalent, we either
need to ignore the corresponding to null string or we need to insert a new initial
state at beginning whose output os 0; the other row elements in this case
would remain the same.

12. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur

Consider Sample Transition table
Present State
Next State
a = 0 a = 1
State Output State Output
-> q0 q3 0 q1 1
q1 q0 1 q3 0
q2 q2 1 q2 0
q3 q1 0 q0 1

13. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur

Solution: After applying the conversion steps, we get two states ( q1 and q2) that are
associated with different outputs (0 and 1). so we split both states into q10 , q11 and q20,
q21.
Now the transition table becomes
 
Present State
Next State
a = 0 a = 1
State Output State Output
-> q0 q3 0 q11 1
q10 q0 1 q3 0
q11 q0 1 q3 0
q20 q21 1 q20 0
q21 q21 1 q20 0
q3 q10 0 q0 1

14. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur

Here 
whole row of q1 is copied to q10 , q11 and whole row of q2 is copied to
q20 and q21 of the sample transition table of mealy machine.
The outputs of the next state columns of q1 and q2 are depend on the
previous output. For ex. in the first row, q1 becomes q11 because the
out of q1 is 1. in the fourth row, q2 becomes q21 because the output of
the q2 is 1. and in the subsequent column q2 becomes q20 because the
output of q2 in that column was 0. and so on
 
now in moore machine format, we copied all the states and common
output because in moore machine. the outputs of the next state are
common.
 

15. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur

Present State
Next State
Output
a = 0 a = 1
-> q0 q3 q11 1
q10 q0 q3 0
q11 q0 q3 1
q20 q21 q20 0
q21 q21 q20 1
q3 q10 q0 0
This table is moore machine table corresponding to the sample mealy
machine.
 

16. Conversion from Mealy machine to
Moore machine
08/20/14Er. Deepinder Kaur

Exercise : convert the following mealy machine to corresponding
moore machine
Present State
Next State
a = 0 a = 1
State Output State Output
->q0 q1 0 q3 0
q1 q3 1 q2 0
q2 q4 1 q0 0
q3 q0 0 q4 1
q4 q2 0 q1 1

17. Conversion from Moore machine to Mealy
machine
08/20/14Er. Deepinder Kaur

For understanding the conversion of moore to mealy machine, let us take an
example:
 
suppose the moore machine transition table is:
 
Present State
Next State
Output
a = 0 a = 1
-> q0 q3 q1 1
q1 q0 q3 0
q2 q2 q2 0
q3 q1 q0 1

18. Conversion from Moore machine to Mealy
machine
08/20/14Er. Deepinder Kaur

Solution: First of all take the mealy machine transition table format, i.e.,
Present State
Next State
a = 0 a = 1
State Output State Output

19. Conversion from Moore machine to Mealy
machine
08/20/14Er. Deepinder Kaur

Next step is to copy all the  moore machine transition table states into mealy
machine transition table format
Present State
Next State
a = 0 a = 1
State Output State Output
-> q0 q3 q1
q1 q0 q3
q2 q2 q2
q3 q1 q0

20. Conversion from Moore machine to Mealy
machine
08/20/14Er. Deepinder Kaur

Now in the moore machine, the output of the q0 is 1. so make the
output of q0 in the mealy machine next state column of the above
table is 1. same process is repeated for q1, q2 and q3.
Present State
Next State
a = 0 a = 1
State Output State Output
-> q0 q3 q1
q1 q0 1 q3
q2 q2 q2
q3 q1 q0 1

21. Conversion from Moore machine to Mealy
machine
08/20/14Er. Deepinder Kaur

After repeating the above process for q1,q2 and q3 states, the final
mealy machine transition table is: 
Present State
Next State
a = 0 a = 1
State Output State Output
-> q0 q3 1 q1 0
q1 q0 1 q3 1
q2 q2 0 q2 0
q3 q1 0 q0 1

22. Conversion from Moore machine to Mealy
machine
08/20/14Er. Deepinder Kaur

Exercise :  convert the following Moore machine into mealy
machine:
Present State
Next State
Output
a = 0 a = 1
-> q0 q1 q0 0
q1 q2 q3 1
q2 q3 q2 0
q3 q0 q1 1