Il non determinismo è una delle idee più feconde della teoria della computazione, e il modo migliore per incontrarlo è attraverso gli automi a stati finiti. Un automa non deterministico, o NFA (Nondeterministic Finite Automaton), può avere più mosse possibili nello stesso momento, oppure nessuna. Sembra un modello più potente del DFA; in realtà riconosce esattamente gli stessi linguaggi. Capire perché è un ottimo esercizio di ragionamento.
Che cosa cambia rispetto al DFA
Un NFA è ancora una quintupla (Q, Σ, δ, q₀, F), ma la funzione di transizione ha una forma diversa:
δ: Q × (Σ ∪ {ε}) → P(Q)
dove P(Q) è l'insieme delle parti di Q. Le differenze sono tre:
- da uno stato, leggendo un simbolo, si può andare in più stati contemporaneamente;
- si può andare in nessuno stato: quel ramo di calcolo muore;
- esistono le ε-transizioni, mosse che avvengono senza leggere alcun simbolo.
Un NFA accetta una stringa se esiste almeno un percorso di calcolo che, consumato tutto l'input, termina in uno stato accettante. I percorsi che falliscono non contano.
Due modi di immaginare il non determinismo
Il primo modo è pensare che la macchina «indovini» sempre la scelta giusta. Il secondo, più concreto, è immaginare che a ogni bivio la macchina si duplichi e segua tutti i rami in parallelo: la stringa è accettata se almeno una copia arriva a destinazione.
Il secondo punto di vista è quello che porta direttamente alla simulazione deterministica: invece di seguire una copia alla volta, si tiene traccia dell'insieme di stati in cui potrebbe trovarsi la macchina in quel momento.
Un esempio: «il terzultimo simbolo è 1»
Consideriamo il linguaggio delle stringhe su {0, 1} in cui il terzultimo simbolo è 1. Un NFA lo riconosce con quattro stati:
- q0: legge qualsiasi simbolo e resta in q0; leggendo 1 può anche «scommettere» che quello sia il terzultimo e passare a q1;
- q1: con qualsiasi simbolo va in q2;
- q2: con qualsiasi simbolo va in q3;
- q3: stato accettante, senza transizioni uscenti.
L'automa è semplicissimo da scrivere perché sfrutta l'indovinare. Un DFA per lo stesso linguaggio deve invece ricordare gli ultimi tre simboli letti, quindi ha bisogno di 2³ = 8 stati. In generale, per «l'n-esimo simbolo dalla fine è 1» l'NFA ha n + 1 stati, mentre ogni DFA equivalente ne richiede almeno 2ⁿ.
La costruzione dei sottoinsiemi
Il teorema di equivalenza afferma che per ogni NFA esiste un DFA che riconosce lo stesso linguaggio. La dimostrazione è costruttiva e si chiama costruzione dei sottoinsiemi (subset construction).
Prima serve il concetto di ε-chiusura: l'ε-chiusura di un insieme di stati S è l'insieme degli stati raggiungibili da S usando soltanto ε-transizioni, compresi quelli di S.
Il DFA si costruisce così:
- Ogni stato del DFA è un sottoinsieme degli stati dell'NFA.
- Lo stato iniziale del DFA è l'ε-chiusura di {q₀}.
- Dallo stato S, leggendo il simbolo a, si va nell'ε-chiusura dell'unione di δ(q, a) per ogni q in S.
- Uno stato del DFA è accettante se contiene almeno uno stato accettante dell'NFA.
- Si generano solo gli stati raggiungibili, partendo da quello iniziale e procedendo per esplorazione.
Il punto 5 è importante in pratica: in teoria gli stati possibili sono 2^|Q|, ma spesso quelli effettivamente raggiungibili sono molti meno.
Seguire la costruzione su un caso piccolo
Prendiamo un NFA su {a, b} con stati p, q, r, dove p è iniziale e r è accettante, e le transizioni: da p con a si va in {p, q}, da p con b in {p}, da q con b in {r}. Riconosce le stringhe che terminano con «ab».
- Stato iniziale: {p}.
- {p} con a → {p, q}; {p} con b → {p}.
- {p, q} con a → {p, q}; {p, q} con b → {p, r}.
- {p, r} con a → {p, q}; {p, r} con b → {p}.
Si ottengono tre stati raggiungibili, e l'unico accettante è {p, r}, perché contiene r. Il DFA risultante è corretto ed è anche già minimo.
Perché il non determinismo è utile
Se NFA e DFA sono equivalenti, perché studiare gli NFA? Per tre ragioni concrete:
- Compattezza: come si è visto, un NFA può essere esponenzialmente più piccolo.
- Composizione: unire, concatenare o iterare linguaggi è immediato con le ε-transizioni. È la strada standard per trasformare un'espressione regolare in automa (costruzione di Thompson).
- Ponte concettuale: lo stesso schema, «esiste un percorso che accetta», ritorna nelle macchine di Turing non deterministiche e nella definizione della classe NP. Lì però non sappiamo se il non determinismo si possa eliminare con un costo solo polinomiale: è, in sostanza, la domanda P vs NP.
In sintesi
- Un NFA può avere più transizioni, nessuna transizione o ε-transizioni, e accetta se almeno un ramo di calcolo accetta.
- NFA e DFA riconoscono esattamente la stessa classe: i linguaggi regolari.
- La costruzione dei sottoinsiemi trasforma un NFA in DFA usando insiemi di stati come stati.
- Il costo può essere esponenziale: per alcuni linguaggi ogni DFA equivalente ha almeno 2ⁿ stati.
- Il non determinismo semplifica le costruzioni e anticipa idee centrali della complessità.
