L'automa a stati finiti deterministico, abbreviato DFA (Deterministic Finite Automaton), è il modello di calcolo più semplice che si studia in teoria della computazione. È una macchina senza memoria esterna: conosce soltanto lo stato in cui si trova e il simbolo che sta leggendo. Proprio questa povertà di risorse lo rende utile, perché ci obbliga a chiederci con precisione che cosa si può calcolare con una quantità di memoria fissata in anticipo.
La definizione formale
Un DFA è una quintupla (Q, Σ, δ, q₀, F) dove:
- Q è un insieme finito di stati;
- Σ è l'alfabeto, cioè l'insieme finito dei simboli di input;
- δ: Q × Σ → Q è la funzione di transizione, che a ogni coppia (stato, simbolo) associa esattamente uno stato;
- q₀ ∈ Q è lo stato iniziale;
- F ⊆ Q è l'insieme degli stati di accettazione.
La parola «deterministico» si riferisce proprio a δ: per ogni stato e per ogni simbolo esiste una e una sola mossa possibile. Non ci sono scelte, non ci sono transizioni mancanti, non ci sono mosse che avvengono senza leggere un simbolo.
Come si esegue un DFA
L'automa riceve una stringa w = a₁a₂…aₙ. Parte da q₀, legge a₁ e passa a δ(q₀, a₁), poi legge a₂ e così via. Quando la stringa è finita, guarda lo stato raggiunto: se appartiene a F la stringa è accettata, altrimenti è rifiutata. Il calcolo dura sempre esattamente n passi, uno per simbolo, e termina sempre.
L'insieme di tutte le stringhe accettate si chiama linguaggio riconosciuto dall'automa, e si indica con L(M). I linguaggi riconoscibili da almeno un DFA sono detti linguaggi regolari.
Un esempio concreto: numeri binari divisibili per 3
Supponiamo di voler riconoscere le stringhe sull'alfabeto {0, 1} che, lette come numeri binari, sono multipli di 3. L'idea chiave è tenere traccia del resto della divisione per 3 del numero letto finora. Se il resto attuale è r e leggiamo il bit b, il nuovo numero vale 2·valore + b, quindi il nuovo resto è (2r + b) mod 3.
Servono quindi tre stati, uno per ogni resto possibile:
| Stato | Legge 0 | Legge 1 |
|---|---|---|
| r0 (iniziale, accettante) | r0 | r1 |
| r1 | r2 | r0 |
| r2 | r1 | r2 |
Proviamo con la stringa 110, che vale 6. Si parte da r0; leggendo 1 si va in r1; leggendo 1 si torna in r0; leggendo 0 si resta in r0. Lo stato finale è accettante: 6 è divisibile per 3. Con 101, che vale 5, il percorso è r0 → r1 → r2 → r2, e la stringa viene rifiutata.
Il DFA non ricorda il numero, che può essere enorme, ma solo un riassunto di dimensione limitata. Progettare un automa significa chiedersi quale riassunto basta per decidere.
Come si progetta un DFA
Nel mio lavoro, quando devo costruire un automa a mano, seguo un metodo in quattro passi:
- Stabilire che cosa ricordare. Si elencano le informazioni minime sul prefisso letto che servono per la decisione finale (un resto, l'ultimo simbolo visto, quante volte è comparsa una lettera, fino a un massimo).
- Assegnare uno stato a ogni situazione. Ogni combinazione rilevante di queste informazioni diventa uno stato.
- Scrivere tutte le transizioni. Per ogni stato e ogni simbolo si decide dove andare. Se una situazione rende impossibile accettare, si aggiunge uno stato «pozzo» che non porta mai all'accettazione.
- Verificare con casi limite. La stringa vuota, stringhe di un solo simbolo, stringhe che quasi soddisfano la proprietà.
Un errore frequente è dimenticare il pozzo: in un DFA in senso stretto ogni stato deve avere una transizione per ogni simbolo.
Che cosa un DFA non può fare
Poiché il numero di stati è finito, un DFA non può contare senza limiti. Il linguaggio delle stringhe della forma aⁿbⁿ, cioè n lettere a seguite dallo stesso numero di b, non è regolare: per confrontare il numero di b con il numero di a l'automa dovrebbe ricordare n, che non è limitato. La dimostrazione rigorosa si ottiene con il pumping lemma o con il teorema di Myhill-Nerode.
Questa limitazione non è un difetto, ma una garanzia. Un DFA usa memoria costante e tempo lineare: per questo è alla base di analizzatori lessicali nei compilatori, protocolli di comunicazione descritti come macchine a stati, validatori di formati semplici e controllori di dispositivi embedded.
Proprietà utili dei linguaggi regolari
Dai DFA discendono alcune proprietà molto pratiche:
- Complemento: basta scambiare stati accettanti e non accettanti per ottenere un automa che accetta esattamente le stringhe rifiutate prima.
- Intersezione e unione: con la costruzione del prodotto si simulano due automi in parallelo, usando come stati le coppie di stati.
- Problemi decidibili: si può decidere se un DFA accetta almeno una stringa (raggiungibilità di uno stato finale) e se due DFA riconoscono lo stesso linguaggio.
I linguaggi regolari sono così una classe robusta, primo gradino verso automi a pila e macchine di Turing.
In sintesi
- Un DFA è una quintupla con un numero finito di stati e una sola transizione per ogni coppia stato-simbolo.
- Accetta una stringa se, dopo averla letta tutta, si trova in uno stato di accettazione; i linguaggi così riconosciuti sono i regolari.
- Progettare un DFA significa individuare il riassunto finito del prefisso che basta per decidere.
- Non può contare senza limiti: aⁿbⁿ non è regolare.
- Memoria costante e tempo lineare lo rendono prezioso in compilatori, protocolli e sistemi embedded.
