Concept on Mealy Machine

Finite automata and finite state machines got a complete form by the efforts of George H. Mealy at the Bell Labs and Edward F. Moore in IBM around 1960.

Basically, Finite state machines are divided into two parts

(1) Automata without Output

(2) Automata with Output

The machines with output are named Mealy and Moore machines. These machines are either dependent on their present states and present input or only in the Present state only. So let we discuss both in detail. Here let us discuss first The Mealy machine.

The Mealy machine was proposed by George H. Mealy at the Bell Labs in 1960.

Mostly, the finite automata have binary output, i.e., they either accept the string or do not accept. All these are decided on the basis of whether the final state is reached by the initial state or not. Removing this restriction, Let's consider a model where the outputs can be chosen from some other alphabet. The Mealy machine is one type of finite automata with output, where the output depends on the present state and the present input.

The Mealy machine consists of six tuples

M = (Q, Σ, Δ, δ, λ, q0)

where,

Q: finite non-empty set of states

Σ: set of input alphabets

Δ: set of output alphabets

δ: transitional function mapping Q × Σ → Q

λ : output function mapping Q × Σ → Δ

q0: beginning state

The values of the output function F(t) in the most general case are a function of the present state q(t) and present input x(t).

F(T) = λ(q(t), x(t))

where δ is called the output function.

This model is called the “Mealy machine”.

A “Mealy machine” is a six-tuple (Q, Σ, Δ, δ, λ, q0) where all the symbols except λ have the same meaning as discussed in the sections above. λ is the output function mapping Σ x Q into Q.

Consider an example to understand concept about Mealy Machine

Example 1 :

The finite state transducer with Q = {q0, q1}, Σ = {0, 1}, Γ = {a, b, c}, initial state q0, and

δ(q0, 0) = q1, δ(q0, 1) = q0,

δ(q1, 0) = q0, δ(q1, 1) = q1,

θ(q0, 0) = a, θ(q0, 1) = c,

θ(q1, 0) = b, θ(q1, 1) = a

is represented by the graph. This Mealy machine prints out caab when given the input string 1010.

Example 2 :

Construct a Mealy machine M that takes as input strings of 0’s and 1’s. Its output is to be a string of 0’s until the first 1 occurs in the input, at which time it will switch to printing 1’s. This is to continue until the next 1 is encountered in the input when the output reverts to 0. The alternation continues every time a 1 is encountered. For example, FM(0010010) = 0011100.