Indietro

ⓘ Minimizzazione di DFA



                                     

ⓘ Minimizzazione di DFA

In Teoria degli automi è detto minimizzazione di un DFA il procedimento che trasforma un dato automa a stati finiti deterministico nel DFA equivalente che ha il minor numero di stati. Due DFA sono detti equivalenti se riconoscono lo stesso linguaggio formale. Ci sono diversi algoritmi che producono il minimo DFA partendo da uno dato, con diversi metodi e complessità.

                                     

1. DFA minimo

Esiste, per ogni linguaggio regolare che può essere accettato da un DFA, uno e un solo automa minimo, ovvero un DFA che ha il minimo numero di stati. Lavorare sullautoma minimo è conveniente in termini di complessità computazionale per quegli algoritmi che lo utilizzano per i più svariati scopi, come il pattern matching.

Per ridurre un DFA si identificano al suo interno due tipi di stati, che possono essere uniti o eliminati senza che ciò influisca sul linguaggio accettato dallautoma stesso:

  • Stati non distinguibili: stati che non possono essere distinti da un altro stato per nessuna delle possibili stringhe del linguaggio.
  • Stati irraggiungibili: stati dellautoma che in nessun caso possono essere raggiunti dallo stato iniziale; ovvero, stati diversi dallo stato iniziale che non hanno transizioni entranti, o stati in cui ogni transizione entrante parte da uno stato irraggiungibile.

La minimizzazione avviene in tre passi, in cui si rimuovono o si uniscono tra loro gli stati di cui sopra. Essa culmina sempre con leliminazione degli stati non distinguibili, in quanto si tratta delloperazione più dispendiosa.

                                     

2. Stati irraggiungibili

Sia

A = {\displaystyle {\mathcal {A}}=Q,\Sigma,\delta,q_{0},T}

un automa determinista completo. In questa definizione, Q {\displaystyle Q} è linsieme degli stati, Σ {\displaystyle \Sigma } è lalfabeto, δ {\displaystyle \delta } è la funzione di transizione che mappa uno stato ed un simbolo dellalfabeto in uno stato, q 0 {\displaystyle q_{0}} è lo stato iniziale e T {\displaystyle T} è linsieme degli stati terminali accettori.

Due stati p {\displaystyle p} e q {\displaystyle q} appartenenti a Q {\displaystyle Q}, sono detti indistinguibili se tutte le parole w {\displaystyle w} riconosciute da A {\displaystyle {\mathcal {A}}} partendo da p {\displaystyle p} sono anche riconosciute partendo da q {\displaystyle q} e vice-versa. Formalmente, se per ogni parola w {\displaystyle w}:

p ⋅ w ∈ T ⟺ q ⋅ w ∈ T {\displaystyle p\cdot w\in T\iff q\cdot w\in T}.

Due stati sono separabili se non sono inseparabili. Vale il seguente criterio di minimizzazione:

Un automa finito deterministico completo e accessibile è minimo se e soltanto se i suoi stati sono due a due separabili.

Lequivalenza di Nerode è la relazione denotata ∼ {\displaystyle \sim }, sullinsieme degli stati e definita da

q ∼ q ′ ⟺ L q A = L q ′ A {\displaystyle q\sim q\iff L_{q}{\mathcal {A}}=L_{q}{\mathcal {A}}}.

Due stati equivalenti per la precedente relazione sono indistinguibili e vice-versa. Un automa è minimo quando lequivalenza di Nerode è luguaglianza.

                                     

2.1. Stati irraggiungibili Algoritmo del calcolo degli stati raggiungibili/irraggiungibili

Lo stato p {\displaystyle p} di un automa finito deterministico A = {\displaystyle {\mathcal {A}}=Q,\Sigma,\delta,q_{0},T} è irraggiungibile se non esiste alcuna parola w ∈ Σ ∗ {\displaystyle w\in \Sigma ^{*}} per la quale p = δ q 0, w {\displaystyle p=\delta q_{0},w}. Denotiamo qui δ ∗ {\displaystyle \delta ^{*}} lestensione della funzione a tutte le stringhe. Gli stati raggiungibili possono essere ottenuti col seguente algoritmo:

Gli stati irraggiungibili possono essere rimossi dal DFA senza influenzare il linguaggio che questi accetta.

Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →