Moore & Mealy Machine | Theory of Computation (TOC)

Finite Automata with output is always deterministic.

They are of two type:

    1. Moore Machine

    2. Mealy Machine

Moore Machine : 

Moore machine are machine in which output depends on state.

Here it is noted down output only depends on state and there is no final state.

In the the previous topics like DFA's machine are acceptable on the basis of reachability to final node/state from initial node/state, but this restriction is removed in Moore Machine because there is no final state.

Formal Definition of Moore machine :

It is a set of six tuple ( Q , Σ , Δ , δ , λ , q0 )

where :

Q → Finite set of states

Σ → Finite set of input symbol or alphabet

 Δ →Finite set of output symbol or alphabet

δ →Transition function mapping

            Q X Σ→ Q

 λ → Output function

            λ: Q X Δ

 q0→Initial state  

Note : 

Finite automata with output is always deterministic.

In Moore machine if the length of input string is (n) it generate output string of length (n+1).

Construction of Moore Machine:            

Example : Construct a moore machine that print "a" for '01. 

Solution :

For solving this question we just create DFA for this problem because we know how to create a DFA than just associate output with states.when 01 comes print "a"  and for remaining print "b".

Transition table :

For example if string is 0110 than the above moore machine print bbabb

Mealy Machine :

It is a machine in which output depend on state as well as input symbol.

(A , x)→ y

on x input output is generated

Formal Definition of Mealy machine :

It is a set of six tuple ( Q , Σ , Δ , δ , λ , q0 )

where :

Q → Finite set of states

Σ → Finite set of input symbol or alphabet

 Δ →Finite set of output symbol or alphabet

δ →Transition function mapping

            Q X Σ→ Q

 λ → Output function

             λ: Q X Σ → Δ

 q0→Initial state  

Note : 

Finite automata with output is always deterministic.

In Mealy machine if the length of input string is (n) it generate output string of length (n).

  

Construction of Moore Machine:            

Example : Construct a Moore Machine that print "a" for '01. 

Solution : Refer from notes.

Download Complete Notes of Moore & Mealy Machine:         

Moore and Mealy -1 Moore and Mealy -2 Moore and Mealy -3 Moore and Mealy -4 Moore and Mealy -5 Moore and Mealy -6 Moore and Mealy -7 Moore and Mealy -8 Moore and Mealy -9 Moore and Mealy -10 Moore and Mealy -11 Moore and Mealy -12 Moore and Mealy -13 Moore and Mealy -14 Moore and Mealy -15 Moore and Mealy -16 Moore and Mealy -17 Moore and Mealy -18 Moore and Mealy -19