Briefly describe Moore and Mealy machines.

An automation system in which the output depends only on the present input is called a Moore machine. Alternatively, an automaton system in which output depends both on the present input and the present state is called Mealy machine.

            A Moore machine can be defined as a 6-tuple ( S, S₀, Σ, Λ, T, G ) consisting of the following:

·         a finite set of states ( S )

·         a start state (also called initial state) S₀ which is an element of (S)

·         a finite set called the input alphabet ( Σ )

·         a finite set called the output alphabet ( Λ )

·         a transition function (T : S × Σ → S) mapping a state and the input alphabet to the next state

·         an output function (G : S → Λ) mapping each state to the output alphabet

A Moore machine can be regarded as a restricted type of finite state transducer.

The difference between Moore machines and Mealy machines is that in the latter, the output of a transition is determined by the combination of current state and current input. In other words: in a diagram

·         for a Moore machine, each node (state) is labeled with an output value;

·         for a Mealy machine, each arc (transition) is labeled with an output value.

Every Moore machine M is equivalent to the Mealy machine with the same states and transitions and the output function that takes each state-input pair (q,x) to G_M(q), where G_M is M's output function.

Conversely, every Mealy machine M is equivalent to the Moore machine with as its states all pairs of S × Λ of M, and as its transitions ((q,o),y) → (T_M(q,y),G_M(q,y)), and as output function (q,o) → o, where T_M and G_M are M's transition resp. output functions.

L(R) = { (0 + 1)^m000(0+1)ⁿ  m ≥ 0 and n ≥ 0}.