Minimizzazione degli stati di un automa

Lezione precedente: Teoremi sugli automi a stati finiti

Corso: Materia:Informatica Teorica

Prossima lezione: Proprietà di chiusura dei linguaggi regolari

Introduzione

Al termine della lezione precedente, dopo aver dimostrato il teorema di Myhill e Nerode, ci siamo resi conto che la relazione esistente tra automi a stati finiti e linguaggi è più complicata del previsto; anche se è facile immaginare che ogni riconoscitore a stati finiti sia associato ad un linguaggio, ci siamo siamo resi conto che il contrario non è vero e che esiste la possibilità che uno stesso linguaggio venga riconosciuto da più di un automa a stati finiti.

Per non restare nel vago consideriamo i diagrammi a stati di tre accettori che riconoscono il medesimo linguaggio, visibili nelle immagini sottostanti.

Tutti e tre gli automi riconoscono il linguaggio $L=\left\{a^{n}b^{m}:n\in \mathbb {N} ,m\in \mathbb {N} \setminus \left\{0\right\}\right\}$.

Come si può notare i tre automi sono strutturalmente diversi a causa di alcuni elementi che non combaciano: il numero degli stati, il tipo degli stati (nel terzo automa ci sono due stati di accettazione) o la disposizione delle transizioni (il terzo automa dispone di un solo autoanello).

Se si potesse immaginare un insieme contenente tutti gli accettori a stati finiti verrebbe spontaneo partizionarlo in modo che ogni sottoinsieme contenga tutti e solo gli automi che riconoscono un dato linguaggio regolare.

La teoria delle relazioni binarie ci dice che la partizione può essere interpretata come l'insieme quoziente indotto da una relazione binaria di equivalenza definita sull'insieme che contempla tutti gli accettori; i tre automi presentati poc'anzi sarebbero quindi equivalenti.

Lo scopo di questa lezione è proprio introdurre una relazione di equivalenza tra automi che sia in linea con quanto appena presentato e di indagare a fondo gli effetti provocati dalla sua introduzione. Come vedremo, infatti, non solo la relazione ci permetterà di suddividere l'insieme degli accettori in classi di equivalenza, ma ci offrirà anche la possibilità di identificare, per ogni classe di equivalenza, un unico accettore da utilizzare come rappresentante della classe stessa: l'accettore canonico. Come vedremo, l'accettore canonico dispone sempre del numero minimo di stati e può tranquillamente essere definito come l'automa che riconosce il linguaggio regolare $L$ impiegando il minor numero di stati.

Il ruolo dell'accettore canonico inteso come rappresentante di una classe di equivalenza assume un'importanza particolare nell'ambito dell'informatica teorica. In generale, la relazione tra linguaggi regolari ed automi a stati finiti è di tipo uno-a-molti: per ogni linguaggio regolare esistono molti accettori a stati finiti in grado di riconoscerlo. Avere la possibilità di identificare uno solo di tali accettori per ogni linguaggio regolare permette di stabilire una relazione uno-a-uno, ossia una corrispondenza biunivoca, tra l'insieme dei linguaggi regolari e l'insieme degli accettori canonici.

Grazie a questa considerazione abbiamo la garanzia che ogni risultato teorico riguardante i linguaggi regolari sarà valido anche per gli accettori a stati finiti, e viceversa. È quindi evidente l'importanza concettuale insita nella ricerca degli automi accettori a stati minimi.

La parte iniziale della presente lezione servirà, come al solito, per preparare il terreno all'identificazione dell'automa a stati minimi e sarà basata sull'introduzione di una relazione di equivalenza tra automi e del concetto di automi isomorfi.

Il cuore della lezione concerne l'enunciazione e la dimostrazione dei teoremi di esistenza ed unicità dell'automa a stati minimi. Come abbiamo già avuto modo di sottolineare, questo risultato ha un grande valore concettuale in quanto garantisce che, per ogni linguaggio regolare, l'automa a stati minimi esiste ed è unico; tuttavia il teorema non spiega come sia possibile identificare l'automa a stati minimi, né come si possa eventualmente trasformare un automa non canonico nel suo equivalente a stati minimi.

La seconda parte della lezione, quindi, verrà dedicata alla presentazione di due algoritmi di minimizzazione degli stati che hanno trovato (e trovano tutt'ora) ampia applicazione.

Automi equivalenti

Si consideri un linguaggio regolare $L\subseteq I^{*}$ e due accettori a stati finiti $A_{1}=(Q_{1},I,\delta _{1},q_{i1},F_{1})$ e $A_{2}=(Q_{2},I,\delta _{2},q_{i2},F_{2})$. I due automi sono equivalenti se e solo se accettano il medesimo linguaggio $L$.

Formalmente i due automi saranno equivalenti quando le due condizioni sottostanti saranno verificate:

• $\forall x\in I^{*},(x\in L)\Rightarrow (\delta _{1}^{*}(q_{i1},x)\in F_{1}\land \delta _{2}^{*}(q_{i2},x)\in F_{2})$;
• $\forall x\in I^{*},(x\notin L)\Rightarrow (\delta _{1}^{*}(q_{i1},x)\notin F_{1}\land \delta _{2}^{*}(q_{i2},x)\notin F_{2})$.

Introdurre un'equivalenza sull'insieme degli accettori a stati finiti significa anche indurre una partizione costituita dall'insieme quoziente.

Ogni sottoinsieme appartenente alla partizione costituisce una classe di equivalenza e raccoglie tutti gli accettori che sono in grado di riconoscere il medesimo linguaggio.

Lavorare con le classi di equivalenza può essere vantaggioso in quanto, se dovesse essere necessario dimostrare una proprietà per l'intera classe, in determinate condizioni sarebbe possibile dimostrare che la proprietà vale per uno solo degli elementi della classe, generalizzando poi il risultato attraverso l'equivalenza.

Affinché tale approccio possa funzionare è indispensabile scegliere con cura il rappresentante della classe, per evitare di incorrere in situazioni delicate dove la proprietà da dimostrare vale solamente per il rappresentante e non per il resto della classe.

Quando esiste un criterio oggettivo che permette di identificare in modo univoco il rappresentante di una classe di equivalenza, tale rappresentante prende il nome di elemento canonico.

Ci chiediamo, a questo punto, se nel contesto degli accettori a stati finiti e con la relazione di equivalenza introdotta in precedenza sia sempre possibile identificare l'elemento canonico delle classi di equivalenza, ossia ci chiediamo se esiste l'accettore canonico.

Dimostreremo due risultati di grande importanza: l'esistenza dell'accettore canonico e la sua unicità.

Successivamente svilupperemo una tecnica che ci permetterà di costruire l'accettore a stati minimi di un generico linguaggio regolare $L$. Come vedremo, per raggiungere questi obiettivi tornerà utile la conoscenza del teorema di Myhill - Nerode.

Automi isomorfi

Consideriamo due automi accettori a stati finiti che siano completi ed equivalenti. Indichiamo i due automi con $A_{1}=(Q_{1},I,\delta _{1},q_{i1},F_{1})$ e $A_{2}=(Q_{2},I,\delta _{2},q_{i2},F_{2})$. Diciamo che i due automi sono isomorfi quando, data una funzione biunivoca $f:Q_{1}\rightarrow Q_{2}$, valgono le seguenti considerazioni:

• $\forall q\in Q_{1},f(q)=p\in Q_{2}$;
• $\forall q\in Q_{1},\forall a\in I,f(\delta _{1}(q,a))=\delta _{2}(f(q),a)$;
• $(q\in F_{1})\iff (f(q)\in F_{2})$.

Cerchiamo ora di dare significato alle tre proprietà, analizzando anzitutto la prima e l'ultima perché sono le più facili.

La prima proprietà ci garantisce che ad ogni stato del primo automa è associato uno stato del secondo automa, tramite la funzione biunivoca.

L'ultima proprietà ci assicura che la funzione biunivoca assocerà gli stati finali del primo automa agli stati finali del secondo automa, una condizione indispensabile per garantire che i due automi riconoscano lo stesso linguaggio regolare, come richiesto dall'ipotesi di equivalenza.

Un altro aspetto fondamentale per garantire il riconoscimento dello stesso linguaggio regolare riguarda la funzione di transizione ed è esattamente questo lo scopo della seconda proprietà. Per comprenderla meglio cerchiamo di chiarire il contesto in cui nasce.

Consideriamo quindi quattro stati $q\in Q_{1},s\in Q_{1},p\in Q_{2},t\in Q_{2}$ ed un generico simbolo $a\in I$. Grazie all'ipotesi di completezza degli automi, le rispettive funzioni di transizione saranno definite per ogni possibile simbolo d'ingresso e per ogni stato. Supponiamo ora che $f(q)=p$ e che $f(s)=t$; immaginiamo anche che $\delta _{1}(q,a)=s$ e che $\delta _{2}(p,a)=t$. Vediamo cosa succede applicando la seconda proprietà:

• $f(\delta _{1}(q,a))=\delta _{2}(f(q),a)$;
• $f(s)=\delta _{2}(p,a)$;
• $t=t$.

Come si vede, al termine del procedimento si è ottenuta l'identità. In realtà, l'unico modo affinché si verifichi tale condizione è che le funzioni di transizione dei due automi siano strutturate proprio come abbiamo immaginato. Quindi introdurre la seconda condizione obbliga i due automi a disporre di funzioni di transizione opportunamente strutturate.

Il concetto di isomorfismo tra automi verrà utilizzato, nel contesto della minimizzazione degli stati, per dimostrare l'unicità dell'automa minimo.

Esistenza ed unicità dell'automa a stati minimi

Occupiamoci anzitutto di provare che l'automa a stati minimi esiste ed è unico per ogni linguaggio regolare $L$. Per questo motivo enunciamo e dimostriamo i teoremi di esistenza ed unicità dell'automa a stati minimi.

Teorema di esistenza dell'automa a stati minimi

Consideriamo un linguaggio regolare $L\subseteq I^{*}$ ed un insieme contenente gli accettori a stati finiti $A=(Q,I,\delta ,q_{i},F)$ che sono completi e riconoscono $L$ come linguaggio macchina. È sempre possibile identificare un automa ${\overline {A}}=({\overline {Q}},I,{\overline {\delta }},{\overline {q_{i}}},{\overline {F}})$ che è in grado di riconoscere il linguaggio $L$ impiegando il numero minimo di stati.

Dimostrazione

Durante la dimostrazione del teorema di Myhill - Nerode abbiamo utilizzato due relazioni di equivalenza: $R_{M}$ definita sull'insieme degli accettori che hanno $L$ come linguaggio macchina e $R_{L}$ sull'insieme delle stringhe appartenenti al linguaggio.

Abbiamo anche visto che la relazione $R_{M}$ è un raffinamento di $R_{L}$, aspetto che ci ha permesso di concludere che l'indice di $R_{L}$ sarà sempre minore o uguale all'indice di $R_{M}$.

Questo significa che la relazione $R_{L}$ induce un numero di classi di equivalenza che è sempre minore, o tutt'al più uguale, al numero di classi di equivalenza indotte da $R_{M}$.

Sappiamo che il numero di classi di equivalenza indotte da $R_{M}$ è pari al numero degli stati dell'automa; inoltre, sempre durante la dimostrazione del teorema di Myhill - Nerode abbiamo costruito un accettore a stati finiti impiegando come stati proprio le classi di equivalenza indotte da $R_{L}$. Come conseguenza, confrontare gli indici delle due relazioni significa in realtà confrontare il numero di stati di due automi.

Grazie a questa osservazione possiamo concludere che l'automa costruito sfruttando le classi di equivalenza indotte da $R_{L}$ avrà sempre meno stati, o al limite lo stesso numero di stati, rispetto agli altri accettori del linguaggio $L$.

Il teorema è dunque dimostrato.

Teorema di unicità dell'automa a stati minimi

Per ogni linguaggio regolare $L\subseteq I^{*}$ esiste uno ed un solo accettore a stati finiti $A=(Q,I,\delta ,q_{i},F)$ dotato del numero minimo di stati, a meno di un isomorfismo tra gli stati.

Dimostrazione

Ipotizzando l'esistenza di due automi equivalenti a stati minimi $A=(Q_{1},I,\delta _{1},q_{i1},F_{1})$ e $B=(Q_{2},I,\delta _{2},q_{i2},F_{2})$, dimostriamo che devono essere necessariamente isomorfi.

Entrambi gli automi sono a stati minimi, quindi ad ognuno dei loro stati può essere associata una delle classi di equivalenza $[x]$ definita dalla relazione $R_{L}$.

Considerando che i due automi sono equivalenti, il linguaggio $L$ in questione è lo stesso, dunque saranno le stesse anche le classi di equivalenza; in particolare, il numero di classi di equivalenza è identico nei due casi.

Grazie a questa osservazione è possibile immaginare una funzione biunivoca $f:Q_{1}\rightarrow Q_{2}$; se davvero i due automi sono isomorfi, allora devono verificare le tre condizioni che abbiamo introdotto poc'anzi.

• $\forall [x],f([x])=[y]\in Q_{2}$;
• $\forall [x]\in Q_{1},\forall a\in I,f(\delta _{1}([x],a))=\delta _{2}(f([x]),a)$;
• $[x]\in F_{1}\iff f([x])\in F_{2}$.

La prima è verificata semplicemente applicando la funzione biunivoca ad uno qualunque degli stati del primo automa. La terza condizione è un po' più delicata: dato che i due automi riconoscono il medesimo linguaggio, le classi di equivalenza che identificano le stringhe accettate devono essere per forza le stesse nei due casi. Veniamo ora alla seconda condizione:

• $\forall [x]\in Q_{1},\forall a\in I,f(\delta _{1}([x],a))=\delta _{2}(f([x]),a)$;
• $\forall [x]\in Q_{1},\forall a\in I,f([xa])=\delta _{2}([y],a)$;
• $\forall [x]\in Q_{1},\forall a\in I,[ya]=[ya]$.

Possiamo concludere che i due automi sono isomorfi. Visto che questo risultato vale comunque si scelgano due automi a stati minimi equivalenti, il teorema di unicità è dimostrato.

Costruire l'automa a stati minimi

La dimostrazione dei precedenti teoremi ci permette di essere certi circa l'esistenza dell'accettore canonico; inoltre sappiamo che tale automa dispone del numero minimo di stati. Il teorema, tuttavia, non offre alcuno strumento per la costruzione dell'automa a stati minimi, dunque dovremo identificare almeno un algoritmo in grado di raggiungere questo obiettivo.

Esamineremo due algoritmi in grado di costruire l'accettore canonico; sebbene le soluzioni che analizzeremo affrontino il problema da punti di vista differenti, essi partono dalle medesime premesse.

Proprio per questo motivo sarà necessario anteporre alla presentazione degli algoritmi un'analisi dei concetti chiave della minimizzazione.

Gli stati superflui

Affermare che un automa è dotato del numero minimo di stati equivale ad affermare che tutti gli altri automi dispongono di stati aggiuntivi che, in un certo senso, sono superflui.

Un algoritmo di minimizzazione avrà quindi tre obiettivi:

1. identificare gli stati superflui dell'automa da minimizzare;
2. rimuovere gli stati superflui;
3. ristrutturare la funzione di transizione.

In generale, quando si parla di stati superflui si intendono due tipologie di stato:

1. gli stati irraggiungibili: sono tali tutti quegli stati che non rappresentano mai lo stato prossimo di una transizione. Gli stati irraggiungibili si possono rimuovere dall'automa senza alterarne la funzionalità;
2. gli stati equivalenti o indistinguibili: due stati p e q sono equivalenti quando i linguaggi $L_{p}$ e $L_{q}$ coincidono, ossia $L_{p}=L_{q}$. Gli stati equivalenti non vengono rimossi, bensì confluiscono in un unico stato;

È interessante notare che anche gli stati irraggiungibili possono essere interpretati in termini di linguaggi: in effetti, dato che non vengono mai raggiunti durante l'evoluzione della computazione, tali stati sono caratterizzati dal riconoscimento del linguaggio vuoto; formalmente, indicando con $q$ uno stato irraggiungibile, potremo scrivere $L_{q}=\emptyset$.

Esaminiamo ora i due tipi di stati superflui, analizzandoli con maggior profondità.

Gli stati irraggiungibili

Nella succinta definizione che è appena stata introdotta si è visto che uno stato è irraggiungibile quando non esiste alcuna transizione che conduca ad esso.

Come conseguenza, nessuna delle transizioni uscenti da uno stato irraggiungibile potrà mai essere percorsa e lo stato stesso potrà essere eliminato dall'automa senza influenzarne il funzionamento.

Per comprendere quest'ultima affermazione, riprendiamo due degli automi presentati nell'introduzione alla lezione.

Nel secondo automa è presente lo stato $q_{2}$ e nessuna transizione porta ad esso; come conseguenza, le due transizioni che partono da $q_{2}$ verso $q_{0}$ e $q_{1}$ non saranno mai percorribili.

Proprio per questo motivo lo stato $q_{2}$ e le transizioni ad esso relative possono essere rimosse dall'automa senza influenzare le computazioni. Tra l'altro, come si può notare ispezionando i diagrammi degli stati, la rimozione dello stato $q_{2}$ porta il secondo automa a coincidere con il primo.

Se da un punto di vista grafico è facile rimuovere lo stato e le relative transizioni, vale la pena di riflettere su cosa accada quando si opera con la rappresentazione algebrica. Nel caso dell'automa che stiamo analizzando, la rappresentazione algebrica della funzione di transizione è visibile nella tabella sottostante.

	a	b
$q_{0}$	$q_{0}$	$q_{1}$
$q_{1}$	-	$q_{1}$
$q_{2}$	$q_{0}$	$q_{1}$

In questo contesto rimuovere lo stato superfluo consiste nella cancellazione della riga della tabella corrispondente allo stato irraggiungibile.

Un algoritmo per l'identificazione degli stati irraggiungibili

Un semplice algoritmo per identificare gli stati irraggiungibili di un automa si potrebbe strutturare come segue:

1. preparare una lista degli stati raggiungibili;
2. inizializzare la lista, specificando che nessuno stato è raggiungibile (condizione iniziale);
3. scorrere la tabella della funzione di transizione e, per ogni stato che viene incontrato, segnarlo come stato raggiungibile sulla lista.

Al termine, gli elementi della lista che non saranno stati indicati come raggiungibili saranno proprio gli stati irraggiungibili.

Gli stati equivalenti

Come abbiamo visto durante la dimostrazione del teorema di Myhill - Nerode, ogni stato di un accettore a stati finiti è in grado di riconoscere un insieme di stringhe; tali stringhe vengono considerate equivalenti e l'insieme che le raccoglie è una classe di equivalenza.

In realtà, siccome la classe di equivalenza è un sottoinsieme di $I^{*}$, è anche un linguaggio; più precisamente, indicando con $q$ un generico stato di un accettore a stati finiti potremo scrivere: $L_{q}=\left\{x\in I^{*}:\delta ^{*}(q_{i},x)=q\right\}$.

Questa considerazione può essere sfruttata per definire un'equivalenza tra stati: due stati $p$ e $q$ sono equivalenti quando i linguaggi da essi riconosciuti coincidono, ossia $L_{p}=L_{q}$.

Per non restare nel vago, facciamo un esempio riprendendo gli accettori a stati finiti introdotti a inizio lezione e concentrandoci sul primo e sul terzo.

Osservando il primo automa si nota come il linguaggio associato allo stato $q_{0}$ sia composto dalla stringa vuota e da tutte le stringhe formate da sole $a$: $L_{q_{0}}=\left\{a^{n}|n\in \mathbb {N} \right\}$. Nello stesso automa il linguaggio associato allo stato $q_{1}$ è composto da tutte le stringhe formate da sole $b$, esclusa la stringa vuota: $L_{q_{1}}=\left\{b^{n}|n\in \mathbb {N} ,n>0\right\}$.

Osservando il secondo automa si riscontrano invece i seguenti linguaggi:

• $L_{q_{0}}=\left\{a^{n}|n\in \mathbb {N} \right\}$;
• $L_{q_{1}}=\left\{b^{n}|n\in \mathbb {N} ,n>0\right\}$;
• $L_{q_{2}}=\left\{b^{n}|n\in \mathbb {N} ,n>0\right\}$.

Come si può notare, i linguaggi riconosciuti dagli stati $q_{1}$ e $q_{2}$ sono identici; per questo motivo i due stati sono equivalenti.

Introdurre una relazione di equivalenza sull'insieme degli stati implica indurre una partizione in classi di equivalenza dell'insieme stesso. Nell'esempio soprastante, la relazione di equivalenza introdotta sull'insieme degli stati induce una partizione in due classi; formalmente, possiamo scrivere $P=\left\{\left\{q_{0}\right\},\left\{q_{1},q_{2}\right\}\right\}$.

Gli elementi della partizione, e dunque i due insiemi elencati, rappresentano gli stati di un nuovo accettore: si nota come gli stati $q_{1}$ e $q_{2}$, essendo equivalenti, si sono fusi, confluendo in un unico stato.

È interessante notare come la fusione di due stati equivalenti produca effetti anche sulle transizioni: in particolare, vengono abolite tutte le transizioni tra stati equivalenti, mentre permangono quelle dirette da e verso altri stati dell'automa.

Il diagramma degli stati dell'automa, dopo la fusione degli stati equivalenti, è visibile nell'immagine sottostante.

Dal diagramma si può notare come strutturalmente questo nuovo accettore coincida con quello proposto all'inizio, a meno di una ridenominazione degli stati.

Abbiamo visto che la fusione di più stati riduce il numero di stati dell'automa; affinché questo procedimento possa attuarsi è però necessario che gli stati in questione siano equivalenti.

L'esempio proposto ha permesso di identificare l'equivalenza fra stati analizzando le proprietà delle classi di equivalenza indotte sul linguaggio macchina ma non sempre questo procedimento è semplice da svolgere. Questa osservazione ci permette di concludere che è necessario identificare almeno un metodo che ci dia la possibilità di stabilire l'equivalenza fra stati in modo semplice e magari senza ricorrere al linguaggio macchina.

L'algoritmo induttivo

L'algoritmo che presenteremo è senza dubbio il più famoso; noto con il nome di table-filling algorithm, si basa sui concetti di distinguibilità e indistinguibilità degli stati e sul noto principio d'induzione.

Prima di presentare i dettagli dell'algoritmo analizziamo alcune informazioni utili per comprenderlo a fondo e contestualizzarne l'impiego.

Distinguibilità ed indistinguibilità degli stati

Consideriamo un automa accettore a stati finiti $A=(Q,I,\delta ,q_{i},F)$; cerchiamo di capire, almeno intuitivamente, come si fa a capire quando due stati $p$ e $q$ di tale automa sono distinguibili.

Indichiamo con $x\in I^{*}$ una stringa di simboli che permette all'automa di portarsi nello stato $p$: $\delta ^{*}(q_{i},x)=p$ ed un'analoga stringa $y\in I^{*}$ tale che $\delta (q_{i},y)=q$.

I due stati $p$ e $q$ sono distinguibili se e solo se esiste una stringa $s$ tale che esattamente una delle due stringhe $xs$ e $ys$ porta l'accettore in uno stato finale. Formalmente, due stati $p\in Q$ e $q\in Q$ sono distinguibili quando si verifica la seguente condizione:

$(x\in I^{*}|\delta ^{*}(q_{i},x)=p)\land (y\in I^{*}|\delta ^{*}(q_{i},y)=q)\Rightarrow \exists s\in I^{*}|((\delta ^{*}(q_{i},xs)\in F)\land (\delta ^{*}(q_{i},ys)\notin F)\lor ((\delta ^{*}(q_{i},xs)\notin F)\land (\delta ^{*}(q_{i},ys)\in F))$

La relazione di distinguibilità così definita non può essere una relazione di equivalenza in quanto per essa non vale la proprietà riflessiva; infatti è impossibile che uno stato sia distinguibile da se stesso.

È più interessante, quindi, concentrarsi sulla relazione di indistinguibilità degli stati, che si definisce semplicemente negando la relazione precedente. Intuitivamente, due stati sono indistinguibili quando non è possibile trovare alcuna stringa che, concatenata alle stringhe riconosciute dagli stati, conduca l'automa a due situazioni finali contrastanti. Formalmente:

$(x\in I^{*}|\delta ^{*}(q_{i},x)=p)\land (y\in I^{*}|\delta ^{*}(q_{i},y)=q)\Rightarrow \forall s\in I^{*}|((\delta ^{*}(q_{i},xs)\in F)\land (\delta ^{*}(q_{i},ys)\in F)\lor ((\delta ^{*}(q_{i},xs)\notin F)\land (\delta ^{*}(q_{i},ys)\notin F))$

La relazione di indistinguibilità degli stati è un'equivalenza; infatti:

• proprietà riflessiva: uno stato è sempre indistinguibile da se stesso;
• proprietà simmetrica: se uno stato $p$ è indistinguibile da $q$, allora anche $q$ sarà indistinguibile da $p$;
• proprietà transitiva: se uno stato $p$ è indistinquibile da $q$ e lo stato $q$ è indistinguibile da $r$, allora anche lo stato $p$ è indistinguibile da $r$.

Trattandosi di un'equivalenza, la relazione di indistinguibilità partiziona l'insieme degli stati suddividendolo in classi di equivalenza; così facendo diventa possibile identificare gli stati indistinguibili. Evidentemente gli stati che non saranno indistinguibili saranno tutti e soli gli stati distinguibili.

La tecnica impiegata per identificare gli stati indistinguibili consiste nel controllare l'indistinguibilità di ogni possibile coppia di stati. Teoricamente, dunque, il punto di partenza dovrebbe essere una tabella a doppia entrata in cui sia sulle righe sia sulle colonne si trovano disposti gli stati dell'automa. Ad esempio, nel caso di un automa $A=(Q,I,\delta ,q_{i},F)$ dotato dell'insieme di stati $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4}\right\}$, la tabella di partenza potrebbe essere la seguente.

-	$q_{0}$	$q_{1}$	$q_{2}$	$q_{3}$	$q_{4}$
$q_{0}$	$(q_{0},q_{0})$	$(q_{0},q_{1})$	$(q_{0},q_{2})$	$(q_{0},q_{3})$	$(q_{0},q_{4})$
$q_{1}$	$(q_{1},q_{0})$	$(q_{1},q_{1})$	$(q_{1},q_{2})$	$(q_{1},q_{3})$	$(q_{1},q_{4})$
$q_{2}$	$(q_{2},q_{0})$	$(q_{2},q_{1})$	$(q_{2},q_{2})$	$(q_{2},q_{3})$	$(q_{2},q_{4})$
$q_{3}$	$(q_{3},q_{0})$	$(q_{3},q_{1})$	$(q_{3},q_{2})$	$(q_{3},q_{3})$	$(q_{3},q_{4})$
$q_{4}$	$(q_{4},q_{0})$	$(q_{4},q_{1})$	$(q_{4},q_{2})$	$(q_{4},q_{3})$	$(q_{4},q_{4})$

Dato che stiamo valutando una relazione di equivalenza, possiamo sfruttarne le proprietà per semplificare la nostra ricerca. In particolare, visto che l'equivalenza è sempre riflessiva, sappiamo già che gli elementi della diagonale principale saranno coppie di stati indistinguibili; possiamo perciò rimuoverli dalla tabella, ottenendo il risultato seguente.

-	$q_{0}$	$q_{1}$	$q_{2}$	$q_{3}$	$q_{4}$
$q_{0}$	-	$(q_{0},q_{1})$	$(q_{0},q_{2})$	$(q_{0},q_{3})$	$(q_{0},q_{4})$
$q_{1}$	$(q_{1},q_{0})$	-	$(q_{1},q_{2})$	$(q_{1},q_{3})$	$(q_{1},q_{4})$
$q_{2}$	$(q_{2},q_{0})$	$(q_{2},q_{1})$	-	$(q_{2},q_{3})$	$(q_{2},q_{4})$
$q_{3}$	$(q_{3},q_{0})$	$(q_{3},q_{1})$	$(q_{3},q_{2})$	-	$(q_{3},q_{4})$
$q_{4}$	$(q_{4},q_{0})$	$(q_{4},q_{1})$	$(q_{4},q_{2})$	$(q_{4},q_{3})$	-

Inoltre, sfruttando la proprietà simmetrica possiamo concludere che se i due stati $(q_{i},q_{j})$ sono indistinguibili, allora anche $(q_{j},q_{i})$ lo saranno. Per questo motivo è sufficiente considerare solo una parte dell'intera tabella; tradizionalmente si conserva intatta la parte diagonale inferiore, visibile qui sotto.

-	$q_{0}$	$q_{1}$	$q_{2}$	$q_{3}$	$q_{4}$
$q_{0}$	-	-	-	-	-
$q_{1}$	$(q_{1},q_{0})$	-	-	-	-
$q_{2}$	$(q_{2},q_{0})$	$(q_{2},q_{1})$	-	-	-
$q_{3}$	$(q_{3},q_{0})$	$(q_{3},q_{1})$	$(q_{3},q_{2})$	-	-
$q_{4}$	$(q_{4},q_{0})$	$(q_{4},q_{1})$	$(q_{4},q_{2})$	$(q_{4},q_{3})$	-

Dato un automa dotato di $k$ stati, viene lasciato per esercizio il calcolo di quante coppie vanno valutate.

L'algoritmo che stiamo per esaminare si occuperà di identificare, attraverso una successione di marcature, quali coppie di stati sono equivalenti.

L'algoritmo

L'algoritmo che stiamo per presentare è noto anche con i nomi di algoritmo delle marcature o table-filling algorithm e propone una strategia induttiva per l'identificazione degli stati distinguibili.

Come vedremo, una volta che il processo di marcatura sarà ultimato, ogni coppia di stati non marcata rappresenterà due stati indistinguibili e potrà essere accorpata in un unico nuovo stato.

Il processo di marcatura applica la tecnica dell'induzione matematica; è dunque necessario definire il passo base ed il passo di induzione in modo opportuno. Indicando con $\equiv$ la relazione di indistinguibilità avremo:

1. passo base: $(p\in F)\land (q\notin F)\Rightarrow p\not \equiv q$;
2. passo di induzione: $\exists a\in I|\delta (p,a)\not \equiv \delta (q,a)\Rightarrow p\not \equiv q$ .

Il passo base viene eseguito per primo, mentre il passo di induzione viene ripetuto fintantoché sarà possibile aggiungere nuove marcature alla tabella.

Cerchiamo ora di dare un senso ai due criteri appena introdotti; in generale, la tecnica impiegata per dimostrare la distinguibilità di due stati consiste nella ricerca di una stringa che, concatenata con quelle già elaborate dall'automa, crea le condizioni affinché l'accettore completi la sua evoluzione in due stati palesemente distinti: uno finale e l'altro no.

Identificare la stringa per tentativi è un compito troppo dispersivo, quindi l'algoritmo propone un approccio più strutturato, costruendo la stringa un passo per volta; chiaramente ad ogni passo verrà aggiunto un solo simbolo ed è proprio questo il succo del passo d'induzione.

Inizialmente la stringa da concatenare non dispone ancora di nessun simbolo e dunque è la stringa vuota. In questa situazione si possono dunque distinguere solamente gli stati finali da quelli che non lo sono; questo spiega il passo base.

Esempio

Come al solito, un esempio vale più di mille parole. Supponiamo dunque di voler minimizzare un automa accettore a stati finiti $A=(Q,I,\delta ,q_{i},F)$; il suo diagramma degli stati, come pure la sua descrizione algebrica, sono visibili qui di seguito.

• $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4},q_{5}\right\}$;
• $I=\left\{a,b\right\}$;
• $q_{i}=q_{0}$;
• $F=\left\{q_{1},q_{2},q_{4}\right\}$;
• infine, la funzione di transizione $\delta$ è definita dalla tabella sottostante.

	a	b
$\rightarrow q_{0}$	$q_{3}$	$q_{1}$
$*q_{1}$	$q_{2}$	$q_{5}$
$*q_{2}$	$q_{2}$	$q_{5}$
$q_{3}$	$q_{0}$	$q_{4}$
$*q_{4}$	$q_{2}$	$q_{5}$
$q_{5}$	$q_{5}$	$q_{5}$

Una veloce scansione del diagramma, o della funzione di transizione, permettono di comprendere che questo automa è privo di stati irraggiungibili e quindi, se fosse minimizzabile, l'unica possibilità che rimarrebbe per ridurre il numero dei suoi stati consisterebbe nell'identificazione, e successiva fusione, degli stati indistinguibili.

Prepariamo dunque una tabella simile a quella vista in precedenza, da impiegare per il confronto delle coppie di stati.

-	$q_{0}$	$q_{1}$	$q_{2}$	$q_{3}$	$q_{4}$	$q_{5}$
$q_{0}$	-	-	-	-	-	-
$q_{1}$		-	-	-	-	-
$q_{2}$			-	-	-	-
$q_{3}$				-	-	-
$q_{4}$					-	-
$q_{5}$						-

Svolgiamo ora il passo base, che consiste nel marcare le coppie di stati che sono distinguibili anche senza concatenazione di una stringa; si tratterà di tutte le coppie in cui uno solo dei due elementi sarà uno stato finale. Le marcature riportate sulla tabella saranno indicate dal numero 0, per indicare che si tratta del passo base. La tabella risultante dopo questa prima fase è visibile qui di seguito.

-	$q_{0}$	$q_{1}$	$q_{2}$	$q_{3}$	$q_{4}$	$q_{5}$
$q_{0}$	-	-	-	-	-	-
$q_{1}$	0	-	-	-	-	-
$q_{2}$	0		-	-	-	-
$q_{3}$		0	0	-	-	-
$q_{4}$	0			0	-	-
$q_{5}$		0	0		0	-

A questo punto abbiamo completato il passo base e possiamo svolgere la prima iterazione del passo d'induzione. Una rapida occhiata alla tabella ci permette di comprendere che in questa iterazione sarà necessario svolgere sei confronti: uno per ogni casella libera.

Ogni confronto viene svolto per ogni simbolo dell'alfabeto d'ingresso.

Primo confronto - stati $q_{1}$ e $q_{2}$.

a	b
$\delta (q_{1},a)=q_{2}$	$\delta (q_{1},b)=q_{5}$
$\delta (q_{2},a)=q_{2}$	$\delta (q_{2},b)=q_{5}$

Come si può vedere dalla tabella, in corrispondenza di entrambi i simboli i due stati evolvono addirittura negli stessi stati prossimi; sono evidentemente indistinguibili e quindi non vanno marcati.

Secondo confronto - stati $q_{3}$ e $q_{0}$.

a	b
$\delta (q_{3},a)=q_{0}$	$\delta (q_{3},b)=q_{4}$
$\delta (q_{0},a)=q_{3}$	$\delta (q_{0},b)=q_{1}$

In corrispondenza all'ingresso $a$ lo stato $q_{3}$ evolve nello stato $q_{0}$ e viceversa; dato che questa coppia non è stata marcata come distinguibile, si può andare oltre. La seconda coppia di stati, generata a partire dall'ingresso $b$, è $(q_{4},q_{1})$ e non è stata precedentemente marcata, dunque anche in questo caso nessuna marcatura va aggiunta alla tabella.

Terzo confronto - stati $q_{1}$ e $q_{4}$.

a	b
$\delta (q_{1},a)=q_{2}$	$\delta (q_{1},b)=q_{5}$
$\delta (q_{4},a)=q_{2}$	$\delta (q_{4},b)=q_{5}$

Non ci sono nuove marcature da registrare.

Quarto confronto - stati $q_{2}$ e $q_{4}$.

a	b
$\delta (q_{2},a)=q_{2}$	$\delta (q_{2},b)=q_{5}$
$\delta (q_{4},a)=q_{2}$	$\delta (q_{4},b)=q_{5}$

Non si registra nessuna marcatura aggiuntiva.

Quinto confronto - stati $q_{0}$ e $q_{5}$.

a	b
$\delta (q_{0},a)=q_{3}$	$\delta (q_{0},b)=q_{1}$
$\delta (q_{5},a)=q_{5}$	$\delta (q_{5},b)=q_{5}$

La coppia $(q_{1},q_{5})$ è stata marcata durante il passo base, quindi anche $(q_{0},q_{5})$ va marcata.

Sesto confronto - stati $q_{3}$ e $q_{5}$.

a	b
$\delta (q_{3},a)=q_{0}$	$\delta (q_{3},b)=q_{4}$
$\delta (q_{5},a)=q_{5}$	$\delta (q_{5},b)=q_{5}$

La coppia $(q_{4},q_{5})$ è stata marcata durante il passo base, quindi anche $(q_{3},q_{5})$ va marcata.

Dopo aver riportato le marcature sulla tabella, si ottiene il risultato sottostante.

-	$q_{0}$	$q_{1}$	$q_{2}$	$q_{3}$	$q_{4}$	$q_{5}$
$q_{0}$	-	-	-	-	-	-
$q_{1}$	0	-	-	-	-	-
$q_{2}$	0		-	-	-	-
$q_{3}$		0	0	-	-	-
$q_{4}$	1			1	-	-
$q_{5}$	1	0	0	1	0	-

Al termine di questa seconda iterazione si osserva che quasi tutte le coppie di stati sono state marcate. All'appello ne mancano quattro: la coppia $(q_{1},q_{2})$, la coppia $(q_{0},q_{3})$, la coppia $(q_{4},q_{2})$ e la coppia $(q_{4},q_{1})$.

Esaminando nuovamente queste quattro coppie si può notare che è impossibile aggiungere ulteriori marcature alla tabella.

La tabella che si ottiene al termine della seconda iterazione del passo induttivo è identica alla precedente e questo ci autorizza a fermarci. Il processo termina con quattro coppie non marcate, di cui andremo ad approfondire il significato.

Le coppie non marcate indicano stati indistinguibili, quindi $q_{0}$ è indistinguibile da $q_{3}$, $q_{1}$ è indistinguibile da $q_{2}$, $q_{1}$ è indistinguibile da $q_{4}$ e $q_{2}$ è indistinguibile da $q_{4}$.

Dato che la relazione di indistinguibilità è un'equivalenza siamo certi che vale la proprietà transitiva; come conseguenza, se è vero che $q_{1}$ è indistinguibile da $q_{2}$ e che $q_{2}$ è indistinguibile da $q_{4}$, allora è anche vero che $q_{1}$ è indistinguibile da $q_{4}$.

Grazie a questa osservazione è possibile accorpare i tre stati in un unico nuovo stato, indicato con $\left\{q_{1},q_{2},q_{4}\right\}$.

È inoltre possibile accorpare i due stati $q_{0}$ e $q_{3}$ in un unico nuovo stato, indicato con $\left\{q_{0},q_{3}\right\}$.

A questo punto è possibile immaginare la struttura dell'automa a stati minimi $M=({\overline {Q}},I,{\overline {\delta }},{\overline {q_{i}}},{\overline {F}})$. In particolare:

• ${\overline {Q}}=\left\{\left\{q_{0},q_{3}\right\},\left\{q_{1},q_{2},q_{4}\right\},\left\{q_{5}\right\}\right\}$;
• ${\overline {q_{i}}}=\left\{q_{0},q_{3}\right\}$;
• ${\overline {F}}=\left\{\left\{q_{1},q_{2},q_{4}\right\}\right\}$.

Dato che l'alfabeto di ingresso rimane invariato, l'unico elemento mancante per la definizione dell'automa a stati minimi è la funzione di transizione che può essere ricavata dalla precedente, tenendo presenti i seguenti principi:

• tutte le transizioni che conducono da uno stato ad uno stato equivalente diventano autoanelli;
• quando diverse transizioni conducono a più stati equivalenti, vengono fatte tutte confluire verso un unico stato.

Seguendo questi principi si ottiene la seguente funzione di transizione ${\overline {\delta }}$

	a	b
$\rightarrow \left\{q_{0},q_{3}\right\}$	$\left\{q_{0},q_{3}\right\}$	$\left\{q_{1},q_{2},q_{4}\right\}$
$*\left\{q_{1},q_{2},q_{4}\right\}$	$\left\{q_{1},q_{2},q_{4}\right\}$	$\left\{q_{5}\right\}$
$\left\{q_{5}\right\}$	$\left\{q_{5}\right\}$	$\left\{q_{5}\right\}$

Concludiamo l'esempio proponendo l'immagine del diagramma degli stati dell'automa minimizzato.

L'algoritmo delle partizioni

Questo algoritmo è stato introdotto da John Hopcroft nel 1971 e ha il pregio di migliorare le prestazioni dell'algoritmo precedente. Rispetto a quest'ultimo, tuttavia, la filosofia è differente: anziché confrontare le coppie di stati, Hopcroft propone una strategia basata sul concetto di partizione, applicato all'insieme degli stati dell'automa da minimizzare.

Analogamente all'algoritmo precedente anche in questo caso si segue un approccio iterativo; è dunque rilevante identificare la condizione iniziale, in cui la partizione prevede due soli sottoinsiemi: quello degli stati di accettazione e quello degli altri stati.

A questo punto si verifica se davvero questa partizione può rappresentare l'automa a stati minimi e, in caso contrario, si costruisce una nuova partizione, dotata di un numero più alto di sottoinsiemi; in questo caso, più precisamente, la nuova partizione viene creata a partire da almeno uno dei sottoinsiemi della partizione precedente. In generale, quindi, possiamo pensare all'evoluzione dell'algoritmo di Hopcroft come ad un successione di partizioni, l'ultima delle quali identifica l'automa a stati minimi.

Per fare in modo che la successione converga è importante stabilire due criteri:

• criterio di stabilità: determina quando è il caso di creare una nuova partizione;
• criterio di convergenza: stabilisce quando la partizione trovata corrisponde a quella dell'automa a stati minimi.

Il concetto di stabilità

Nel contesto dell'algoritmo di Hopcroft il concetto di stabilità può essere interpretato in due modi:

• stabilità di un sottoinsieme: un sottoinsieme di una partizione è stabile quando per ogni stato in esso contenuto e per ogni ingresso possibile, lo stato prossimo appartiene sempre ad un medesimo sottoinsieme della partizione;
• stabilità di una partizione: una partizione è stabile quando tutti i suoi sottoinsiemi sono stabili.

La definizione di stabilità di un sottoinsieme è decisamente la più complicata da intuire, dunque la approfondiremo presentando un esempio ed un controesempio che ne chiariscano il significato.

Esempio di sottoinsieme stabile

Consideriamo l'accettore a stati finiti che abbiamo minimizzato in precedenza, usando l'algoritmo delle marcature.

In particolare ci concentriamo sullo stato iniziale che prevede una partizione caratterizzata da due sottoinsiemi: uno contenente tutti gli stati di accettazione, l'altro contenente gli altri stati; formalmente la partizione si potrà scrivere come $P=\left\{F,Q\setminus F\right\}$.

Dimostriamo ora che il sottoinsieme $F$ è stabile; per ogni stato appartenente al sottoinsieme, determiniamo lo stato prossimo in corrispondenza di tutti i possibili simboli d'ingresso. Sintetizziamo questa fase creando una tabella, visibile qui sotto.

	$q_{1}$	$q_{2}$	$q_{4}$
$a$	$q_{2}$	$q_{2}$	$q_{2}$
$b$	$q_{5}$	$q_{5}$	$q_{5}$

Come si può notare leggendo la tabella, in corrispondenza al simbolo $a$ i tre stati finali producono uno stato prossimo (in questo caso $q_{2}$) che si trova in un unico sottoinsieme, in questo caso il sottoinsieme $F$.

Analogamente, in corrispondenza al simbolo $b$ lo stato prossimo (in questo caso $q_{5}$) si trova nel sottoinsieme $Q\setminus F$.

Visto che in corrispondenza di tutti i simboli d'ingresso lo stato prossimo prodotto appartiene ad un unico sottoinsieme, possiamo concludere che il sottoinsieme stesso è stabile.

Va sottolineato che il criterio impiegato per la stabilità non richiede che tutti gli stati generino lo stesso stato prossimo; per garantire la stabilità basta che gli stati prossimi generati appartengano tutti ad un medesimo sottoinsieme.

Esempio di sottoinsieme non stabile

Continuiamo ad analizzare l'esempio precedente prendendo in considerazione il sottoinseme $Q\setminus F$ e dimostrando che non è stabile. Come prima, costruiamo una tabella che considera tutti gli stati del sottoinsieme e tutti i possibili ingressi.

	$q_{0}$	$q_{3}$	$q_{5}$
$a$	$q_{3}$	$q_{0}$	$q_{5}$
$b$	$q_{1}$	$q_{4}$	$q_{5}$

Come si può notare leggendo la tabella, in corrispondenza al simbolo $a$ gli stati prossimi appartengono tutti ad uno stesso sottinsieme (in questo caso proprio $Q\setminus F$), mentre nel caso del simbolo $b$ non c'è concordanza in quanto non tutti gli stati prossimi appartengono al medesimo insieme: infatti $q_{1}\in F$, $q_{4}\in F$ ma $q_{5}\in Q\setminus F$.

Proprio per questo motivo il sottoinsieme non è stabile; inoltre, dato che la partizione selezionata contiene un sottoinsieme non stabile, non può a sua volta essere stabile.

L'algoritmo

A questo punto è possibile esaminare in qualche dettaglio l'algoritmo proposto da Hopcroft:

1. Crea una partizione iniziale di due sottoinsiemi: uno con gli stati finali, uno con tutti gli altri stati;
2. Finché la partizione non è stabile:

   per ogni sottoinsieme appartenente alla partizione:

   se il sottoinsieme non è stabile, allora raffina la partizione attuale

3. Ristruttura la funzione di transizione
4. Crea l'automa a stati minimi

Naturalmente questa versione dell'algoritmo è fortemente schematica e va approfondita, specialmente per quanto riguarda l'identificazione dell'instabilità della partizione. Inoltre l'esecuzione efficiente dell'algoritmo di Hopcroft presuppone anche una certa attenzione alle strutture dati impiegate.

Nell'algoritmo si possono riconoscere due fasi principali: la ricerca degli stati minimi (passi 1 e 2) e la ristrutturazione della funzione di transizione (passo 3). Dopo aver identificato gli stati minimi e considerando l'alfabeto d'ingresso, è possibile procedere ad una revisione della funzione di transizione che è concettualmente molto semplice, in quanto lo stato prossimo di ogni transizione dell'automa a stati minimi sarà costituito dalla partizione che contiene lo stato prossimo della transizione che si manifesta nell'automa non minimizzato.

Come al solito vale la pena di chiarirsi le idee attraverso un esempio; considereremo il problema dell'ottimizzazione dello stesso automa a stati minimi su cui abbiamo applicato, in precedenza, l'algoritmo delle marcature.

Esempio

Consideriamo nuovamente l'accettore a stati finiti già minimizzato in precedenza; il suo diagramma degli stati è visibile qui sotto.

• $Q=\left\{q_{0},q_{1},q_{2},q_{3},q_{4},q_{5}\right\}$;
• $I=\left\{a,b\right\}$;
• $q_{i}=q_{0}$;
• $F=\left\{q_{1},q_{2},q_{4}\right\}$;
• infine, la funzione di transizione $\delta$ è definita dalla tabella sottostante.

	a	b
$\rightarrow q_{0}$	$q_{3}$	$q_{1}$
$*q_{1}$	$q_{2}$	$q_{5}$
$*q_{2}$	$q_{2}$	$q_{5}$
$q_{3}$	$q_{0}$	$q_{4}$
$*q_{4}$	$q_{2}$	$q_{5}$
$q_{5}$	$q_{5}$	$q_{5}$

Eseguiamo ora, passo per passo, l'algoritmo di Hopcroft.

Il punto di partenza concerne l'identificazione della partizione iniziale che chiameremo $P_{0}$. Seguendo le caratteristiche dell'algoritmo potremo scrivere $P_{0}=\left\{P_{01},P_{02}\right\}$, dove $P_{01}=\left\{q_{1},q_{2},q_{4}\right\}$ e $P_{02}=\left\{q_{0},q_{1},q_{5}\right\}$ .

Una volta definita la partizione iniziale bisogna capire se è stabile: qualora lo fosse, l'accettore disporrebbe già del numero minimo di stati; in caso contrario sarebbe necessario raffinarla e ripetere il procedimento. Il raffinamento della partizione avverrebbe operando esclusivamente sui sottoinsiemi instabili e lasciando invece intatti gli altri.

Affinché una partizione sia stabile è indispensabile che sia stabile ognuno dei sottoinsiemi che le appartengono; dovremo quindi discutere la stabilità dei due sottoinsiemi $P_{01}$ e $P_{02}$.

Il sottoinsieme $P_{01}$ è stabile: ne abbiamo già parlato quando abbiamo introdotto il concetto di stabilità. Sempre nello stesso contesto abbiamo dimostrato che il sottoinsieme $P_{02}$ non è stabile; come conseguenza la partizione $P_{0}$ non è stabile e va raffinata. Tuttavia, dato che il sottoinsieme $P_{01}$ è già stabile, non verrà coinvolto nel raffinamento.

Per quanto riguarda il sottoinsieme $P_{02}$, si nota che è lo stato $q_{5}$ a comportarsi diversamente dagli altri, pertanto $P_{02}$ viene partizionato come segue: $P_{02}=\left\{P_{021},P_{022}\right\}$, dove $P_{021}=\left\{q_{0},q_{3}\right\}$ e $P_{022}=\left\{q_{5}\right\}$. Con questo cambiamento la partizione $P_{0}$ diventa $P_{1}=\left\{P_{01},P_{021},P_{022}\right\}$

Il sottoinsieme $P_{022}$ è stabile perché è un singleton, mentre $P_{021}$ è stabile e lo si può dedurre esaminando la tabella mostrata nell'esempio precedente. Dato che tutti i sottoinsiemi che costituiscono la partizione $P_{1}$ sono stabili, anche la partizione stessa lo è e l'algoritmo di ottimizzazione termina.

Scrivendo per esteso la partizione stabile si ottiene $P_{1}=\left\{\left\{q_{1},q_{2},q_{4}\right\},\left\{q_{0},q_{3}\right\},\left\{q_{5}\right\}\right\}$, identica a quella ottenuta applicando il precedente algoritmo di ottimizzazione.

Una volta identificato l'insieme degli stati minimi è possibile definire molti degli elementi che caratterizzano l'automa accettore ottimizzato: c'è lo stato iniziale (in questo caso $q_{i}=\left\{q_{0},q_{3}\right\}$) e l'insieme degli stati finali (in questo caso $F=\left\{\left\{q_{1},q_{2},q_{4}\right\}\right\}$).

Lezione precedente: Teoremi sugli automi a stati finiti

Corso: Materia:Informatica Teorica

Prossima lezione: Proprietà di chiusura dei linguaggi regolari