Minimizzazione DFA

Minimizzazione di DFA utilizzando il teorema di Myphill-Nerode

Algoritmo

Input - DFA

Output - DFA ridotto a icona

Step 1- Disegna una tabella per tutte le coppie di stati (Q _i , Q _j ) non necessariamente collegati direttamente [Tutti sono inizialmente non contrassegnati]

Step 2- Considera ogni coppia di stati (Q _i , Q _j ) nel DFA dove Q _i ∈ F e Q _j ∉ F o viceversa e contrassegnale. [Qui F è l'insieme degli stati finali]

Step 3 - Ripeti questo passaggio fino a quando non sarà più possibile contrassegnare gli stati -

Se è presente una coppia non contrassegnata (Q _i , Q _j ), contrassegnala se la coppia {δ (Q _i , A), δ (Q _i , A)} è contrassegnata per qualche alfabeto di input.

Step 4- Combina tutte le coppie non contrassegnate (Q _i , Q _j ) e trasformale in un unico stato nel DFA ridotto.

Esempio

Utilizziamo l'algoritmo 2 per ridurre al minimo il DFA mostrato di seguito.

Step 1 - Disegniamo una tabella per tutte le coppie di stati.

	un	b	c	d	e	f
un
b
c
d
e
f

Step 2 - Contrassegniamo le coppie di stato.

	un	b	c	d	e	f
un
b
c	✔	✔
d	✔	✔
e	✔	✔
f			✔	✔	✔

Step 3- Cercheremo di contrassegnare le coppie di stato, con segno di spunta di colore verde, in modo transitorio. Se inseriamo 1 per indicare "a" e "f", andrà rispettivamente nello stato "c" e "f". (c, f) è già contrassegnato, quindi contrassegneremo la coppia (a, f). Ora, inseriamo 1 per indicare "b" e "f"; andrà rispettivamente allo stato "d" e "f". (d, f) è già contrassegnato, quindi contrassegneremo la coppia (b, f).

	un	b	c	d	e	f
un
b
c	✔	✔
d	✔	✔
e	✔	✔
f	✔	✔	✔	✔	✔

Dopo il passaggio 3, abbiamo combinazioni di stati {a, b} {c, d} {c, e} {d, e} che non sono contrassegnate.

Possiamo ricombinare {c, d} {c, e} {d, e} in {c, d, e}

Quindi abbiamo due stati combinati come - {a, b} e {c, d, e}

Quindi il DFA finale ridotto a icona conterrà tre stati {f}, {a, b} e {c, d, e}

Minimizzazione di DFA utilizzando il teorema di equivalenza

Se X e Y sono due stati in un DFA, possiamo combinare questi due stati in {X, Y} se non sono distinguibili. Due stati sono distinguibili, se c'è almeno una stringa S, tale che uno tra δ (X, S) e δ (Y, S) sia accettabile e un altro non accettante. Quindi, un DFA è minimo se e solo se tutti gli stati sono distinguibili.

Algoritmo 3

Step 1 - Tutti gli stati Q sono divisi in due partizioni - final states e non-final states e sono indicati da P₀. Tutti gli stati in una partizione sono 0 ^° equivalente. Prendi un contatorek e inizializzalo con 0.

Step 2- Incrementa k di 1. Per ogni partizione in P _k , dividi gli stati in P _k in due partizioni se sono k-distinguibili. Due stati all'interno di questa partizione X e Y sono k-distinguibili se c'è un inputS tale che δ(X, S) e δ(Y, S) sono (k-1) -distinguibili.

Step 3- Se P _k ≠ P _k-1 , ripetere il passaggio 2, altrimenti andare al passaggio 4.

Step 4- Combina k- ^esimi set equivalenti e rendili i nuovi stati del DFA ridotto.

Esempio

Consideriamo il seguente DFA:

q	δ (q, 0)	δ (q, 1)
un	b	c
b	un	d
c	e	f
d	e	f
e	e	f
f	f	f

Applichiamo l'algoritmo di cui sopra al DFA precedente -

• P ₀ = {(c, d, e), (a, b, f)}
• P ₁ = {(c, d, e), (a, b), (f)}
• P ₂ = {(c, d, e), (a, b), (f)}

Quindi, P ₁ = P ₂ .

Ci sono tre stati nel DFA ridotto. Il DFA ridotto è il seguente:

Q	δ (q, 0)	δ (q, 1)
(a, b)	(a, b)	(c, d, e)
(c, d, e)	(c, d, e)	(f)
(f)	(f)	(f)