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.

 Also, Study about: 

• Mealy Machine
• Moore Machine
• Rice Theorem
• Brief about Turing Machine
• Multi Dimension Turing Machine
• Multiple Turing Machine
• Parikh Theorem in TOC
• Parse Tree or Derivation Tree
• What do you Understand by Derivation
• MyHill Nerode Theorem
• Minimize Myhill Nerode Theorem
• Push Down Automata
• Know Where we use Automata
• What do you understand by Derivation of Grammar
• What is Context-free Grammar
• Example based on CFG
• Regular Expression in TOC

Also Read, some interview tips

• Why Should I Hire You?
• What are your weaknesses?
• What are your greatest strengths?
• Tell me about yourself.
• What's the reason behind leaving your current position at your company?
• Do You Know how the power of Keywords impacts on Resume?
• Top 8 Proofreading Tips and Techniques in 2022.
• Top Ten Technical Resume Writing Tips in 2022.
• Tips for your resume before you get entry to Job Market
• What Questions you can ask HR during the Interview.
• How to make an impressive resume?
• Best Resume writing Technique.
• What Questions you can ask HR during the Interview.