Due automi diversi possono riconoscere lo stesso linguaggio. Uno può avere tre stati, l'altro trenta. Fra tutti i DFA equivalenti ne esiste uno con il minimo numero di stati, ed è unico a meno di rinominare gli stati. Questo fatto, insieme al teorema di Myhill-Nerode che lo spiega, è uno dei risultati più eleganti della teoria degli automi e ha ricadute pratiche immediate: automi più piccoli occupano meno memoria e si confrontano facilmente.
Stati indistinguibili
Dato un DFA, due stati p e q sono indistinguibili se per ogni stringa w l'automa, partendo da p e leggendo w, accetta esattamente quando, partendo da q e leggendo w, accetta. In altre parole, nessun esperimento sul futuro dell'input può separarli.
Se invece esiste una stringa w che porta uno dei due in uno stato accettante e l'altro no, i due stati sono distinguibili, e w è una stringa testimone.
Gli stati indistinguibili sono ridondanti: si possono fondere in un solo stato senza cambiare il linguaggio. Minimizzare significa proprio:
- eliminare gli stati non raggiungibili dallo stato iniziale;
- fondere fra loro tutti gli stati indistinguibili.
L'algoritmo per raffinamento di partizioni
Il metodo più diffuso per trovare gli stati indistinguibili procede per raffinamenti successivi.
- Si parte da due blocchi: gli stati accettanti e quelli non accettanti. Sono certamente distinguibili dalla stringa vuota.
- Si esamina ogni blocco: due stati dello stesso blocco restano insieme solo se, per ogni simbolo, le loro transizioni portano in stati dello stesso blocco.
- Se un blocco contiene stati che vanno in blocchi diversi, lo si divide.
- Si ripete finché nessun blocco si divide più.
I blocchi finali sono gli stati del DFA minimo. Le transizioni si ereditano da qualunque rappresentante del blocco, perché per costruzione tutti i suoi membri si comportano allo stesso modo.
Un esempio svolto
Consideriamo un DFA su {a, b} con stati 1, 2, 3, 4, 5, dove 1 è iniziale e 4 e 5 sono accettanti. Le transizioni sono:
| Stato | a | b |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 4 | 3 |
| 3 | 2 | 3 |
| 4 | 5 | 3 |
| 5 | 5 | 3 |
Partizione iniziale: {1, 2, 3} e {4, 5}.
Esaminiamo {1, 2, 3}. Con a, lo stato 1 va in 2 (primo blocco), lo stato 2 va in 4 (secondo blocco), lo stato 3 va in 2 (primo blocco). Lo stato 2 si separa: otteniamo {1, 3}, {2}, {4, 5}.
Esaminiamo {1, 3}: con a entrambi vanno in 2, con b entrambi in 3. Restano insieme. Esaminiamo {4, 5}: con a entrambi in 5, con b entrambi in 3. Restano insieme.
Nessun blocco si divide più. Il DFA minimo ha tre stati: A = {1, 3}, B = {2}, C = {4, 5}. Riconosce le stringhe che terminano con «aa», e si vede subito che tre stati bastano: «nessuna a finale», «una a finale», «almeno due a finali».
Il teorema di Myhill-Nerode
Il teorema sposta il discorso dagli automi ai linguaggi. Dato un linguaggio L, due stringhe x e y sono equivalenti rispetto a L se per ogni stringa z vale: xz ∈ L se e solo se yz ∈ L. È una relazione di equivalenza, e conta quante «situazioni diverse» il linguaggio richiede di distinguere.
Il teorema afferma:
L è regolare se e solo se questa relazione ha un numero finito di classi di equivalenza. In tal caso il numero di classi è esattamente il numero di stati del DFA minimo per L.
Il collegamento con l'algoritmo è diretto: ogni stato del DFA minimo corrisponde a una classe di stringhe che il linguaggio non sa distinguere.
Usare Myhill-Nerode per la non regolarità
Il teorema fornisce una tecnica spesso più pulita del pumping lemma. Basta trovare un insieme infinito di stringhe a due a due distinguibili.
Per L = {aⁿbⁿ : n ≥ 0}, consideriamo le stringhe a, aa, aaa, … Prese aⁱ e aʲ con i ≠ j, la stringa z = bⁱ le distingue: aⁱbⁱ è in L, aʲbⁱ no. Le classi sono infinite, quindi L non è regolare. Non ci sono quantificatori alternati né scomposizioni da analizzare.
Perché la minimizzazione conta in pratica
- Equivalenza: per sapere se due DFA riconoscono lo stesso linguaggio si minimizzano entrambi e si verifica che siano identici a meno di rinominare gli stati.
- Efficienza: gli analizzatori lessicali generati automaticamente passano spesso per una fase di minimizzazione, perché la costruzione dei sottoinsiemi può produrre molti stati ridondanti.
- Comprensione: il DFA minimo rivela la struttura essenziale del linguaggio, cioè quante informazioni sul passato bisogna davvero conservare.
In sintesi
- Due stati sono indistinguibili se nessuna stringa futura li separa; fonderli non cambia il linguaggio.
- L'algoritmo parte da accettanti e non accettanti e divide i blocchi finché le transizioni sono coerenti.
- Il DFA minimo è unico a meno di rinominare gli stati.
- Myhill-Nerode: L è regolare se e solo se le classi di stringhe indistinguibili sono finite.
- Trovare infinite stringhe a due a due distinguibili è un modo pulito per provare la non regolarità.
