Mathematical Foundation of Computer Science

DHARM

REGULAR EXPRESSIONS 247

Sol. Construct the output function (λe) table I for the given Moore machine.

Table I

State

Input symbol

0

A

1

1

0

0

0

1

1

B

C

D^10

Similarly construct the transition function (δe) table II.

Table II

State

Input symbol

a

A

b

D

A

D

C

B

A

B
C
D BD
Let we define the equivalent Moore machine (Mo) which is constructed from given Melay
machine i.e.,
Mo = (Qo, Σ, ∆, δo, λo, [A, 0]), where Σ = {a, b}, and 0 ∈ ∆.
l Now set of state Qo = {A, B, C, D} × {0, 1}
= {[A, 0], [A, 1] [B, 0] [B, 1] [C, 0] [C, 1], [D, 0], [D, 1]}
l Determine transition functions δo (using table I & II) i.e.,
δo([A, 0], a) = [δe(A, a), λe(A, a)] = [D, 1]
δo([A, 0], b) = [δe(A, b), λe(A, b)] = [C, 0]
δo([A, 1], a) = [δe(A, a), λe(A, a)] = [D, 1]
δo([A, 1], b) = [δe(A, b), λe(A, b)] = [C, 0]
δo([B, 0], a) = [δe(B, a), λe(B, a)] = [A, 0]
δo([B, 0], b) = [δe(B, b), λe(B, b)] = [B, 1]
δo([B, 1], a) = [δe(B, a), λe(B, a)] = [A, 0]
δo([B, 1], b) = [δe(B, b), λe(B, b)] = [B, 1]
δo([C, 0], a) = [δe(C, a), λe(C, a)] = [D, 0]
δo([C, 0], b) = [δe(C, b), λe(C, b)] = [A, 1]
δo([C, 1], a) = [δe(C, a), λe(C, a)] = [D, 0]
δo([C, 1], b) = [δe(C, b), λe(C, b)] = [A, 1]
δo([D, 0], a) = [δe(D, a), λe(D, a)] = [B, 1]
δo([D, 0], b) = [δe(D, b), λe(D, b)] = [D, 0]
δo([D, 1], a) = [δe(D, a), λe(D, a)] = [B, 1]
δo([D, 1], b) = [δe(D, b), λe(D, b)] = [D, 0]