Scribd
Upload
16 views11 pages

ToC 12

The document discusses the conversion of a Moore machine to an equivalent Mealy machine, outlining the procedure and providing an example. It details how to define the output function for the Mealy machine based on the state transitions of the Moore machine. Additionally, it includes transition tables for both machines to illustrate the conversion process.

Uploaded by

golu.2024012100
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
16 views11 pages

ToC 12

The document discusses the conversion of a Moore machine to an equivalent Mealy machine, outlining the procedure and providing an example. It details how to define the output function for the Mealy machine based on the state transitions of the Moore machine. Additionally, it includes transition tables for both machines to illustrate the conversion process.

Uploaded by

golu.2024012100
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Theory of Computation

Mohd Mursleen
Moore to Mealy Conversion
• If M1= (Q, ∑, ∆, δ, q0, λ) is a Moore machine, then there is a Mealy
machine M2 equivalent to M1.
• Procedure:
• Let M2 = (Q, ∑, ∆, δ, q0, λ' ) and define λ' (q, a) to be λ (δ (q, a)) for
all states q and input symbols a.
• Then M l and M2 enter the same sequence of states on the same input,
and with each transition M2 emits the output that M1 associates with
the state entered.
• Example-
• Construct a Mealy Machine which is equivalent to the Moore machine
given by table below.
• Solution:-
• λ' (q, a) to be λ(δ (q, a))
λ' (q0, 0 ) = λ(δ (q0, 0))
= λ(q3)
=0
λ' (q0, 1) = λ(δ (q0, 1))
= λ(q1)
=1
λ' (q1,0) = λ(δ (q1, 0)) λ' (q1,1) =λ(δ (q1, 1))
=λ (q1) =λ (q2)
=1 =0
λ'(q2, 0) = λ(δ (q2, 0)) λ’ (q2,1) = λ(δ (q2, 1))
=λ (q2) = λ (q3)
=0 =0
λ'(q3,0) = λ(δ (q3, 0)) λ'(q3,1) = λ(δ (q3, 1))
= λ (q3) = λ (q0)
=0 =0
• Mealy Table:-
• Example- The given Moore Machine counts the occurrences of the
sequence ‘abb’ in the given input string. Convert it to its equivalent
Mealy Machine?
• Sol:- Let’s construct the Moore Machine first-
• String that needs to be identified is ‘abb’
• Transition table for moore machine-

a b Output
qo q1 qo 0

q1 q1 q2 0
q2 q1 q3 0
q3 q1 qo 1
• Transition table for Mealy Machine- Based on the Moore machine TT.
- The output for an input symbol for Mealy Machine is decided
from the respective state output in Moore Machine TT.

a b

qo q1, 0 qo, 0

q1 q1, 0 q2, 0

q2 q1, 0 q3, 1

q3 q1, 0 qo, 0

You might also like