Esempio teorema equivalenza Mealy-Moore

Es: automa di Mealy che “riconosce” le sequenze 101 e 110

A: nessun bit della sequenzaB: “1” (primo bit)C: “11” (primi due bit sequenza 2)D: “10” (primi due bit sequenza uno)

Passo uno: Q’ = Qx

A,0

A,1

B,0 C,1

C,0

D,0

D,1

B,1

Funzione ’

A,0

A,1

B,0 C,1

C,0

D,0

D,1

B,1

'((q,b))=b, qQ, b

'((A,0))=0, '((A,1))=1 '((B,0))=0, '((B,1))=1 '((C,0))=0, '((C,1))=1 '((D,0))=0, '((D,1))=1

È il “nome” di uno stato di Moore

0 0

0

0

1 1

1

1

Funzione ’

A,0

A,1

B,0 C,1

C,0

D,0

D,1

B,1

0 0

0

0

1 1

1

1

'((q, b),a) = ((q,a), q,a))

Stato di Moore Stato di Mealy

Stato di Moore

€

'((A,0),0) = (δ(A,0),λ (A,0)) = (A,0)δ '((A,0),1) = (δ(A,1),λ (A,1)) = (A,0)

00

€

'((B,0),0) = (δ(B,0),λ (B,0)) = (D,0)δ '((B,0),1) = (δ(B,1),λ (B,1)) = (C,0)

1

0

€

'((D,0),0) = (δ(D,0),λ (D,0)) = (A,0)δ '((D,0),1) = (δ(D,1),λ (D,1)) = (B,1)

δ '((D,1),0) = (δ(D,0),λ (D,0)) = (A,0)

δ '((D,1),1) = (δ(D,1),λ (D,1)) = (B,1)

1

0

0

1

0

1

€

'((C,0),0) = (δ(C,0),λ (C,0)) = (D,1)δ '((C,0),1) = (δ(C,1),λ (C,1)) = (C,0)

€

'((B,1),0) = (δ(B,0),λ (B,0)) = (D,0)δ '((B,1),1) = (δ(B,1),λ (B,1)) = (C,0)

1

0

Automa di Moore equivalente