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 P0. 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 0 = {(c, d, e), (a, b, f)}
  • P 1 = {(c, d, e), (a, b), (f)}
  • P 2 = {(c, d, e), (a, b), (f)}

Quindi, P 1 = P 2 .

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)