DHARMREGULAR EXPRESSIONS 241From starting state r 0 , if input number is 0 then it returns the number 0((0) 2 mod 3 = 0)
Otherwise, if input number is 1 then output will be 1 (state r 1 number) or ((1) 2 mod 3 = 1).
From state r 1 , if input number is 0, so total input number received at this state is 10 then
machine returns output number 2 (corresponding to state r 2 ) or ((10) 2 mod 3 = 2). At state r 2 ,
received input numbers is 10 then,
l For input string 10 followed by one/more 1 (equivalent number will be either (101,
1011, 10111...) 2 or number (5, 11, 23, ...) 10 ) the output is 2 (corresponding to state r 2 )
or ((101, 1011, ...) 2 mod 3 = 2).
l For input string 10 followed by number 0 then return number is 1 (state r 1 ) or ((100) 2
mod 3 = 2).
l For input string 10 followed by 1* followed by number 0 (equivalent number will be
(1010, 10110, 101110,.....) 2 or (10, 22, 46, ..) 10 ) the return number is 1 ( state r 1 ) which
is again reminder of 3.
At state r 1 possible strings are received,
l 100, or
l 101* 0, i.e., strings are {1010, 10110, 101110,.....}
For state transition r 1 →^ r 0 means that above strings followed by number 1 so that the
final input strings are (1001 or 10101, 101101, 1011101, .......) 2 or (9, 21, 45... ) 10 , in such case
reminder will be zero.9.7 Equivalence of Melay & Moore Automatons.................................................................
When we study the finite automata with output such that a Melay machine and a Moore
machine a general question arises, does both machines are equivalent. Alternatively, we say if
Me is the Melay machine and Mo is the Moore machine then,
Does Me ≡ Mo?
In other words, we may check the equivalence of above machines with respect to the
string generated by them at the output. Let x is the input string, then assume the output of
machines Me and Mo are w and w′ that can be define as,
TMe (x) = w and TMo (x) = w′
Since, | w | ≠ | w′|, it means
TMe (x) ≡/ TMo (x) (for ∀x)
Therefore, Melay machine is not equivalent to Moore machine.
Since these machines are lying in the class finite automaton with output therefore it is
possible to make both these machine equivalent, i.e.,
l Equivalence of a Melay machine to a Moore machine, and
l Equivalence of a Moore machine to a Melay machine.
To make Melay machine equivalent to Moore machine i.e.,
Mo = Me
We must introduce an additional symbol b corresponding to the start state (r 0 ) of the
Moore machine i.e.,
λe (r 0 ) = b then b. TMe (x) = TMo (x)(∀x)
(The Meaning is that start state is the pending state by own)
Eventually, we get the same length of output string from both the machines.