Moore Mealy Machine Conversion

These slides have full understanding about Equivalent Moore Mealy... Having Moore to Mealy conversion and Mealy to Moore conversion...
These slides also describing the concept of Transducers as models of sequential circuits (both w.r.t Moore and Mealy)...
All these concepts are explained with easy examples...

1. Moore, Mealy Machine Conversions & Transducers as models of sequential circuits Presented By: Anum Ayub Sanobir Aslam Aiman Hafeez Tasbeeh Zahra

2. 2 SALAM! I am Anum Ayub I am here to present Conversion of Mealy machine to Moore Machine . Roll No: 101611047

3. Conversion of Moore machine to Mealy Machine Presented By: Anum Ayub ( RollNo : 47 ) 1

4. Introduction of Moore Machine and Mealy Machine A Mealy Machine is an FSM (Finite State Machine) whose output depends on the present state as well as the present input. The value of the output function is a function of the transitions and the changes, when the input logic on the present state is done. While, A Moore machine is also an FSM (Finite State Machine) whose outputs depend on only the present state.   The value of the output function is a function of the current state and the changes at the clock edges, whenever state changes occur. 4

5. Conversion of Moore machine to Mealy Machine Moore machine cannot directly convert to its equivalent Mealy machine because the length of the Moore machine is one longer than the Mealy machine for the given input. To convert Moore machine to Mealy machine , state output symbols are distributed into input symbol paths. 5

6. STEPS to Convert Moore machine to Mealy machine : Step 1:   Take a blank Mealy Machine transition table format. Step 2:   Copy all the Moore Machine transition states into this table format. Step 3:  Check the present states and their corresponding outputs in the Moore Machine state table; if for a state Q i  output is m, copy it into the output columns of the Mealy Machine state table wherever Q i  appears in the next state. 6

7. Example 1: 7 Transition table for above Moore machine is as follows: Present State Next State Output State State q q 1 q q 1 q 1 q 2 q 2 q 1 q 1

8. 8 Present State Next State a b State Output State Output q q 1 q q 1 q 1 q 2 1 q 2 q 1 q Transition table for above Mealy machine is as follows:

9. 9 Transition diagram for Mealy machine will be:

10. Example 2 : 10 Transition table for above Moore machine is as follows: Present State Next State a b A B,0 A,0 B B,0 C,0 C B,0 D,1 D B,0 A,0 A B C D b /0 a/0 a/0 a/0 a/0 b /0 b /0 b/1

11. Example 3: 11 Transition table for above Moore machine is as follows: Present State Next State Output 1 q q 1 q 2 1 q 1 q 3 q 2 q 2 q 2 q 1 1 q 3 q Q 3 1 1 /1 0/1 q 3 q q 1 q 2 1 /1 1 /1 1/0 0/1 0/1 0/0 Present State 1 q q 1 , 0 q 2 , 1 q 1 q 3 , 1 q 2 , 1 q 2 q 2 , 0 q 1 , 0 q 3 q , 0 q 3 , 1 Transition table for above Mealy machine is as follows:

12. Conversion of Mealy machine to Moore Machine Presented By: Sanobir Aslam (RollNo: 79) 2

13. 13 SALAM! I am Sanobir Aslam I am here to present Conversion of Moore machine to Mealy Machine . Roll No: 101611079

14. Conversion of Mealy machine to Moore Machine To convert Mealy machine to Moore machine , we will create a separate state for every new output symbol and according to incoming and outgoing edges are distributed. 14

15. STEPS to Convert Mealy machine to Moore machine : Step 1:   For each state(Qi), calculate the number of different outputs that are available in the transition table of the Mealy machine. Step 2:   Copy state Qi, if all the outputs of Qi are the same. Break qi into n states as Qin, if it has n distinct outputs where n = 0, 1, 2.... Step 3 :  If the output of initial state is 0, insert a new initial state at the starting which gives 1 output. 15

16. Example 1: 16 Transition table for above Mealy machine is as follows: Present State Next State a b State Output State Output q 1 q 1 q 2 q 2 q 2 1 q 3 1 q 3 q 2 q 3 1

17. 17 The state q1 has only one output. The state q2 and q3 have both output 0 and 1. So we will create two states for these states. For q2, two states will be q20(with output 0) and q21(with output 1). Similarly, for q3 two states will be q30(with output 0) and q31(with output 1 ). Transition table for Moore machine will be: Present State Next State Output State Output q 1 q 1 q 2 q 20 q 21 q 30 q 21 q 21 q 30 1 q 30 q 20 q 31 q 31 q 20 q 31 1

18. 18 Transition diagram for Moore machine will be:

19. Example 2: 19 Transition table for above Moory machine is as follows: Present State Next State a b State Output State Output q 1 q 1 1 q 2 q 2 q 4 1 q 4 1 q 3 q 2 1 q 3 1 q 4 q 3 q 1 1

20. 20 For state q1, there is only one incident edge with output 0. So, we don't need to split this state in Moore machine. For state q2, there is 2 incident edge with output 0 and 1. So, we will split this state into two states q20( state with output 0) and q21(with output 1 ). For state q3, there is 2 incident edge with output 0 and 1. So, we will split this state into two states q30( state with output 0) and q31( state with output 1 ). For state q4, there is only one incident edge with output 0. So, we don't need to split this state in Moore machine.

21. 21 Transition table for M ealy machine will be: Present State Next State Output State Output q 1 q 1 q 2 1 q 20 q 4 q 4 q 21 Ø Ø 1 q 30 q 21 q 31 q 31 q 21 q 31 1 q 4 q 3 q 4 1

22. 22 Transition diagram for Mealy machine will be:

23. Transducers as models of Sequential Circuits 3 Presented By: Tasbeeh Zahra (RollNo: 55 ) (Mealy Machine)

24. 24 SALAM! I am Tasbeeh Zahra I am here to present Transducers as models of Sequential C ircuits. Roll No: 101611055

25. Transducers Convert signal from one form to another E . g microphone, speaker etc. 25 NAND DELAY OR OR input output A B Transducer circuit Mealy Machine

26. 26 Truth Tables AND Gate A B A.B 1 1 1 1 1 OR Gate A B A.B 1 1 1 1 1 1 1 NAND Gate A B A.B 1 1 1 1 1 1 1

27. 27 Transducer Circuit NAND DELAY OR OR input output A B Two Points A & B. Total No. OF points=2= No of states = 2^2 = 4 = q0 ,q1,q2,q3 . Already available Points we say Old A & Old B. New Equation New A = input NAND (Old A OR Old B) New B = Old A Output = input OR Old B

28. Transducer-theory of Automata 28 New A = input NAND (Old A OR Old B) New B = Old A Output = input OR Old B State Table States Old A Old B q q 1 1 q 2 1 q 3 1 1

29. 29 Check on both input 0 and 1. State q , Old A = 0 , Old B = 0 New A = input NAND (Old A OR Old B) New A = 0 NAND (0 OR 0) New A = 1 New B = Old A New B = Output = input OR Old B Output = 0 OR 0 Output = At input State q , Old A = 0 , Old B = 0 New A = input NAND (Old A OR Old B) New A = 1 NAND (0 OR 0) New A = 1 New B = Old A New B = Output = input OR Old B Output = 1 OR 0 Output = At input 1

30. 30 Check on both input 0 and 1. State q 1 , Old A = 0 , Old B = 1 New A = input NAND (Old A OR Old B) New A= 0 NAND (0 OR 1) New A = 1 New B = Old A New B = Output = input OR Old B Output = 0 OR 1 Output = 1 At input State q 1 , Old A = 0 , Old B = 1 New A = input NAND (Old A OR Old B) New A = 1 NAND (0 OR 1) New A = New B = Old A New B = Output = input OR Old B Output = 1 OR 1 Output = 1 At input 1

31. 31 Check on both input 0 and 1. State q 2 , Old A = 1 , Old B = 0 New A = input NAND (Old A OR Old B) New A= 0 NAND (1 OR 0) New A = 1 New B = Old A New B = 1 Output = input OR Old B Output = 0 OR 0 Output = At input State q 2 , Old A = 1 , Old B = 0 New A = input NAND (Old A OR Old B) New A = 1 NAND (1 OR 0) New A = New B = Old A New B = 1 Output = input OR Old B Output = 1 OR 0 Output = 1 At input 1

32. 32 Check on both input 0 and 1. State q 3 , Old A = 1 , Old B = 1 New A = input NAND (Old A OR Old B) New A= 0 NAND (1 OR 1) New A = 1 New B = Old A New B = 1 Output = input OR Old B Output = 0 OR 1 Output = 1 At input State q 3 , Old A = 1 , Old B = 1 New A = input NAND (Old A OR Old B) New A = 1 NAND (1 OR 1) New A = New B = Old A New B = 1 Output = input OR Old B Output = 1 OR 1 Output = 1 At input 1

33. 33 State At Input 0 At Input 1 A B Output A B Output q 1 1 1 q 1 1 1 1 q 2 1 1 1 1 q 3 1 1 1 1 1 Transition Table q Mealy Machine 1,1 q 1 q 2 q 3 1,1 1,1 1,1 0,0 0,0 0,1 0,1

34. Transducers as models of Sequential Circuits 4 Presented By: Aiman Hafeez (RollNo: 53 ) (Moore Machine)

35. 35 SALAM! I am Aiman Hafeez I am here to present Transducers as models of Sequential C ircuits. Roll No: 101611053

36. 36 NAND DELAY OR OR input output A B Transducer circuit Moore Machine

37. 37 Truth Tables AND Gate A B A.B 1 1 1 1 1 OR Gate A B A.B 1 1 1 1 1 1 1 NAND Gate A B A.B 1 1 1 1 1 1 1

38. 38 Transducer Circuit Two Points A & B. Total No. OF points=2= No of states = 2^2 = 4 = q0 ,q1,q2,q3 . Already available Points we say Old A & Old B. New Equation New A = input NAND (Old A OR Old B) New B = Old A Output = Old A OR Old B NAND DELAY OR OR input output A B

39. Transducer-theory of Automata 39 New A = input NAND (Old A OR Old B) New B = Old A Output = Old A OR Old B State Table States Old A Old B q q 1 1 q 2 1 q 3 1 1

40. 40 Check on both input 0 and 1. State q , Old A = 0 , Old B = 0 New A = input NAND (Old A OR Old B) New A = 0 NAND (0 OR 0) New A = 1 New B = Old A New B = Output = Old A OR Old B Output =0 OR 0 Output = At input State q , Old A = 0 , Old B = 0 New A = input NAND (Old A OR Old B) New A = 1 NAND (0 OR 0) New A = 1 New B = Old A New B = Output = Old A OR Old B Output = 0 OR 0 Output = At input 1

41. 41 Check on both input 0 and 1. State q 1 , Old A = 0 , Old B = 1 New A = input NAND (Old A OR Old B) New A= 0 NAND (0 OR 1) New A = 1 New B = Old A New B = Output = Old A OR Old B Output = 0 OR 1 Output = 1 At input State q 1 , Old A = 0 , Old B = 1 New A = input NAND (Old A OR Old B) New A = 1 NAND (0 OR 1) New A = New B = Old A New B = Output = Old A OR Old B Output =0 OR 1 Output = 1 At input 1

42. 42 Check on both input 0 and 1. State q 2 , Old A = 1, Old B = 0 New A = input NAND (Old A OR Old B) New A= 0 NAND (1 OR 0) New A = 1 New B = Old A New B = 1 Output = Old A OR Old B Output = 1 OR 0 Output = 1 At input State q 2 , Old A = 1 , Old B = 0 New A = input NAND (Old A OR Old B) New A = 1 NAND (1 OR 0) New A = New B = Old A New B = 1 Output = Old A OR Old B Output = 1 OR 0 Output = 1 At input 1

43. 43 Check on both input 0 and 1. State q 3 , Old A = 1 , Old B = 1 New A = input NAND (Old A OR Old B) New A= 0 NAND (1 OR 1) New A = 1 New B = Old A New B = 1 Output = Old A OR Old B Output = 1 OR 1 Output = 1 At input State q 3 , Old A = 1 , Old B = 1 New A = input NAND (Old A OR Old B) New A = 1 NAND (1 OR 1) New A = New B = Old A New B = 1 Output = Old A OR Old B Output =1 OR 1 Output = 1 At input 1

44. 44 Transition Table q /0 Moore Machine 1 1 1 1 Present State Next State Output Input 0 Input 1 q (1,0) = q 2 (1,0) = q 2 q 1 (1,0) = q 2 (0,0) = q 1 q 2 (1,1) = q 3 (0,1) = q 1 1 q 3 (1,1) = q 3 (0,1) = q 1 1 q 1 /1 q 2 /1 q 3 /1

45. 45 Any questions ? If you have any then GOOGLE IT… ! 😉 Thanks!