Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 245

Table I

State

Input symbol

0

C 0

1

0

1

0

1

0

1

C 1

C 2

And the transition function (δe) is shown in table II.

Table II

State

Input symbol

0

C 0

1

C 0

C 0

C 1

C 1

C 2

C 2

C 1

C 2

Let Mo be the Moore machine which is constructed from given Me then Mo is defined as,

Mo = (Qo, Σ, ∆, δo, λo, [C 0 , b]), where Σ = {0, 1}, b ∈ ∆ = {0, 1}.

l Set Qo = Qe × ∆ = {C 0 , C 1 , C 2 } × {0, 1}

= {[C 0 , 0], [C 0 , 1] [C 1 , 0] [C 1 , 1] [C 2 , 0] [C 2 , 1]}

l Output function (λo) will be determine as,

λo [q, a] = a, for ∀q ∈ Qe and ∀a ∈ Σ

l Determine transition function δo (using table I & II) i.e.,

δo([C 0 , 0], 0) = [δe(C 0 , 0), λe(C 0 , 0)] = [C 0 , 0]

δo([C 0 , 0], 1) = [δe(C 0 , 1), λe(C 0 , 1)] = [C 1 , 1]

δo([C 0 , 1], 0) = [δe(C 0 , 0), λe(C 0 , 0)] = [C 0 , 0]

δo([C 0 , 1], 1) = [δe(C 0 , 1), λe(C 0 , 1)] = [C 1 , 1]

δo([C 1 , 0], 0) = [δe(C 1 , 0), λe(C 1 , 0)] = [C 0 , 1]

δo([C 1 , 0], 1) = [δe(C 1 , 1), λe(C 1 , 1)] = [C 2 , 0]

δo([C 1 , 1], 0) = [δe(C 1 , 0), λe(C 1 , 0)] = [C 0 , 1]

δo([C 1 , 1], 1) = [δe(C 1 , 1), λe(C 1 , 1)] = [C 2 , 0]

δo([C 2 , 0], 0) = [δe(C 2 , 0), λe(C 2 , 0)] = [C 1 , 0]

δo([C 2 , 0], 1) = [δe(C 2 , 1), λe(C 2 , 1)] = [C 2 , 1]

δo([C 2 , 1], 0) = [δe(C 2 , 0), λe(C 2 , 0)] = [C 1 , 0]

δo([C 2 , 1], 1) = [δe(C 2 , 1), λe(C 2 , 1)] = [C 2 , 1]

Hence, we prepare a table III that shows all δo’s for Moore machine.