Automi a stati finiti (FSA)
Come fa un automa a riconoscere una stringa
Nella lezione precedente abbiamo visto come generare le parole di un linguaggio tramite una grammatica. Ma un compilatore ha il problema opposto: data una stringa già scritta nel file sorgente (ad esempio contatore_1 oppure 3.14), deve riconoscere se quella stringa appartiene o meno al linguaggio dei token validi.
Per risolvere questo problema per i linguaggi regolari (Tipo 3 della gerarchia di Chomsky) utilizziamo il modello di calcolo più semplice ed elegante dell’informatica: l’Automa a Stati Finiti (FSA, Finite State Automaton, o in italiano ASF).
Pensa a un distributore automatico o a un tornello della metropolitana: si trova in uno stato iniziale (“Bloccato”); quando riceve un evento di input (“Inserisci biglietto valido”), cambia stato diventando “Sbloccato”; quando riceve l’evento “Passa una persona”, torna nello stato “Bloccato”. L’automa non ha bisogno di un quaderno su cui annotare tutta la sua storia passata: gli basta sapere in quale stato si trova adesso (tra un numero finito di stati possibili) e qual è il simbolo corrente che sta leggendo.
Definizione formale di Automa a Stati Finiti Deterministico (DFA)
Un Automa a Stati Finiti Deterministico (DFA, Deterministic Finite Automaton) è formalmente definito da una quintupla:
dove ciascun elemento ha un ruolo preciso:
-
: insieme finito e non vuoto degli stati interni dell’automa ().
-
: alfabeto di input (insieme finito e non vuoto di simboli che l’automa può leggere sul nastro di ingresso).
-
(Delta): funzione di transizione di stato:
Preso lo stato corrente e il simbolo letto , restituisce l’unico stato successivo in cui si porta l’automa. (L’aggettivo deterministico indica proprio che per ogni coppia la mossa successiva è univocamente determinata).
-
: lo stato iniziale, ovvero lo stato in cui si trova l’automa prima di leggere il primo carattere della stringa.
-
: il sottoinsieme degli stati finali (o di accettazione).
Estensione della funzione di transizione alle stringhe ()
Per descrivere il comportamento dell’automa quando legge un’intera stringa (simbolo dopo simbolo, da sinistra verso destra), estendiamo alla funzione definita per induzione sulla lunghezza della stringa:
-
Caso base (stringa vuota ): se l’automa non legge alcun simbolo, resta nello stato in cui si trova:
-
Passo induttivo (stringa , con e ):
(Prima calcolo in quale stato arrivo dopo aver letto il prefisso , e da quello stato applico con l’ultimo carattere ).
Accettazione di una stringa e Linguaggio Riconosciuto
Una stringa è accettata (o riconosciuta) dall’automa se e solo se, partendo dallo stato iniziale e leggendo tutti i simboli di fino in fondo, l’automa termina in uno stato finale:
L’insieme di tutte le stringhe accettate da è il linguaggio riconosciuto dall’automa , indicato con :
Teorema di Kleene / Chomsky (Tipo 3): Un linguaggio è regolare (generabile da una grammatica di Tipo 3) se e solo se esiste un Automa a Stati Finiti tale che .
Rappresentazione degli Automi: Grafi e Tabelle
Un DFA può essere descritto in due modi equivalenti e immediatamente leggibili:
-
Diagramma degli stati (Grafo orientato etichettato):
- I nodi sono gli stati .
- Lo stato iniziale ha una freccia entrante dall’esterno (
[*] --> q0). - Gli stati finali sono indicati con un doppio cerchio (nei diagrammi Mermaid li indicheremo chiaramente o con una transizione verso
[*]). - Se , si disegna un arco orientato da a con etichetta .
-
Tabella di transizione (Matrice stato simbolo):
- Le righe corrispondono agli stati (segnando con lo stato iniziale e con gli stati finali).
- Le colonne corrispondono ai simboli dell’alfabeto .
- La cella all’incrocio contiene .
Cenni a NFA (Non Determinismo) e Trasduttori (Mealy e Moore)
Automi a Stati Finiti Non Deterministici (NFA)
In un NFA (Nondeterministic Finite Automaton), da uno stato leggendo un simbolo possono partire zero, una o più frecce con la stessa etichetta (e persino frecce spontanee etichettate con ). Formalmente restituisce un insieme di stati possibili. Una stringa è accettata se almeno uno dei cammini possibili termina in uno stato finale.
- Teorema di Rabin-Scott: Ogni NFA può essere trasformato in un DFA equivalente (costruzione per sottoinsiemi). Quindi gli NFA non sono più potenti dei DFA: riconoscono esattamente gli stessi linguaggi (i linguaggi regolari).
Automi con Output (Trasduttori): Macchine di Mealy e di Moore
Un DFA classico produce solo una risposta binaria alla fine della stringa (Accettata / Rifiutata). Se invece vogliamo che l’automa emetta una stringa di output man mano che legge l’input (ad esempio un circuito digitale o un traduttore), usiamo i trasduttori a stati finiti:
- Macchina di Mealy: l’output emesso dipende sia dallo stato corrente sia dal simbolo di input letto (l’output è scritto sulle frecce sotto forma
input / output). - Macchina di Moore: l’output emesso dipende esclusivamente dallo stato raggiunto (l’output è scritto dentro il nodo dello stato).
Dal grafo delle transizioni al riconoscimento
Un distributore accetta sequenze di monete da 10 o 20 centesimi che totalizzano esattamente 30. Rappresentiamo il credito con gli stati 0, 10, 20 e 30. Aggiungiamo lo stato pozzo X per il superamento del prezzo. La dinamica è discreta: ogni moneta produce un solo passo e le transizioni sono definite su un alfabeto finito.
| Stato | Moneta da 10 | Moneta da 20 |
|---|---|---|
| 0 (iniziale) | 10 | 20 |
| 10 | 20 | 30 |
| 20 | 30 | X |
| 30 (finale) | X | X |
| X | X | X |
flowchart LR Start["Inizio"] --> Q0["0"] Q0 -->|"10"| Q10["10"] Q0 -->|"20"| Q20["20"] Q10 -->|"10"| Q20 Q10 -->|"20"| Q30["30 (finale)"] Q20 -->|"10"| Q30 Q20 -->|"20"| X["X"] Q30 -->|"10, 20"| X X -->|"10, 20"| X
Ogni cella della tabella corrisponde a una transizione del grafo, anche quando due etichette condividono una freccia. Con 10, 20 arriviamo in 30. Con 10, 20, 10 arriviamo in X, perché si decide l’accettazione dopo l’ultimo simbolo. In una macchina di Mealy possiamo invece emettere il segnale di consegna sulle transizioni che raggiungono 30. Nella versione di Moore l’uscita è associata allo stato 30. Se si confrontano le sequenze di uscita dei due modelli, va specificato se si osserva anche l’uscita iniziale della macchina di Moore.
Esempi guidati
Esempio 1: Stringhe binarie con un numero PARI di 1
Problema: Costruire un DFA sull’alfabeto che accetti tutte e sole le stringhe contenenti un numero pari di simboli 1 (ricordando che è un numero pari, quindi anche e 000 devono essere accettate!).
Progettazione degli stati:
Quante informazioni dobbiamo ricordare mentre leggiamo la stringa da sinistra a destra? Non ci serve contare (servirebbero infiniti stati!): ci basta ricordare la parità del numero di 1 visti finora! Bastano quindi 2 stati:
- (Stato iniziale e anche FINALE): finora abbiamo letto un numero pari di
1. - (Stato non finale): finora abbiamo letto un numero dispari di
1.
Ogni volta che leggiamo uno 0, la parità degli 1 non cambia (restiamo nello stesso stato). Ogni volta che leggiamo un 1, la parità si inverte (passiamo da a o viceversa).
stateDiagram-v2 direction LR [*] --> qP qP --> qP : 0 qP --> qD : 1 qD --> qD : 0 qD --> qP : 1 qP --> [*] : Stato Finale (Pari)
Tabella di transizione ():
| Stato | Input 0 | Input 1 | Significato dello stato |
|---|---|---|---|
Numero pari di 1 letti (Accettazione) | |||
Numero dispari di 1 letti |
Traccia di esecuzione su :
Su :
Esempio 2: Stringhe binarie che terminano con la sottostringa 01
Problema: Costruire un DFA su che riconosca .
Progettazione degli stati (memoria degli ultimi caratteri visti):
- (Iniziale): non abbiamo ancora visto l’inizio del pattern
01(siamo all’inizio oppure l’ultimo carattere letto era1non preceduto da0). - : l’ultimo carattere letto è stato
0(siamo a metà del pattern01! Se ora arriva0restiamo in perché anche questo nuovo0può fare da inizio di01; se arriva1completiamo01). - (Finale): gli ultimi due caratteri letti sono esattamente
01. Se la stringa finisce qui, accettiamo! Se invece continua: con uno0torniamo in (perché il nuovo0potrebbe iniziare un nuovo01), mentre con un1gli ultimi due caratteri diventano11, quindi torniamo in .
stateDiagram-v2 direction LR [*] --> q0 q0 --> q0 : 1 q0 --> q1 : 0 q1 --> q1 : 0 q1 --> q2 : 1 q2 --> q1 : 0 q2 --> q0 : 1 q2 --> [*] : Finale ("...01")
Esempio 3: Riconoscitore lessicale di Identificatori in C (e implementazione in C!)
In linguaggio C un identificatore (semplificando a lettere L e cifre C) deve iniziare con una lettera L, seguita da zero o più lettere L o cifre C. Se inizia con una cifra C, è un errore lessicale e l’automa finisce in uno stato pozzo (o stato trappola) da cui non può più uscire.
stateDiagram-v2 direction LR [*] --> q0 q0 --> q1 : Lettera (L) q0 --> q_err : Cifra (C) q1 --> q1 : Lettera (L) o Cifra (C) q_err --> q_err : Lettera (L) o Cifra (C) q1 --> [*] : Finale (Identificatore valido)
Ecco come si traduce un DFA direttamente in un programma C pulito:
#include <stdio.h>
int main(void) {
/* Stringa di test: 'a', '1', 'b' -> valida! */
char parola[] = "a1b";
int stato = 0; /* q0 = 0, q1 (finale) = 1, q_err = 2 */
for (int i = 0; parola[i] != '\0'; i++) {
char c = parola[i];
int e_lettera = (c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z');
int e_cifra = (c >= '0' && c <= '9');
if (stato == 0) {
if (e_lettera) stato = 1;
else stato = 2; /* Stato pozzo */
} else if (stato == 1) {
if (e_lettera || e_cifra) stato = 1;
else stato = 2;
}
}
if (stato == 1) {
printf("La stringa '%s' e' un identificatore VALIDO.\n", parola);
} else {
printf("La stringa '%s' NON e' valida.\n", parola);
}
return 0;
}Errori frequenti
Errori da evitare
- Dimenticare di specificare tutte le transizioni in un DFA (funzione incompleta)
In un DFA deterministico, da ogni stato deve uscire esattamente una freccia per ciascun simbolo dell’alfabeto . Se una mossa porta a una stringa irrecuperabilmente errata, bisogna creare esplicitamente uno stato pozzo (trappola) non finale con un cappio su tutti i simboli di .- Sbagliare le transizioni di “ripartenza” nel riconoscimento di sottostringhe
Nell’Esempio 2 (stringhe che terminano con01), molti studenti nello stato (dopo aver letto0), se leggono un altro0, tornano erroneamente a . In questo modo la stringa001verrebbe rifiutata! Se ho letto0e leggo un altro0, l’ultimo carattere visto è comunque uno0, quindi devo rimanere in .- Dimenticare di verificare se la stringa vuota appartiene al linguaggio
Controlla sempre: se , allora lo stato iniziale deve appartenere a (); se , allora .
Esercizi di prova
Esercizio 1. Traccia e linguaggio di un DFA dato (Base)
Dato il DFA con la seguente tabella di transizione:
a) Calcola e indicando se le due stringhe sono accettate.
b) Descrivi a parole il linguaggio riconosciuto dall’automa.
Soluzione
a) Tracce di esecuzione:
Per :
Per :
b) Linguaggio riconosciuto: Per raggiungere bisogna leggere due consecutive (); se si legge una in si torna a . Una volta raggiunto , qualsiasi simbolo mantiene l’automa in . Quindi è il linguaggio di tutte le stringhe su che contengono almeno due consecutive (la sottostringa ).
Esercizio 2. Costruzione di un DFA con stato pozzo (Base)
Disegna in Mermaid e scrivi la tabella di transizione di un DFA sull’alfabeto che accetti tutte e sole le stringhe che iniziano con 01 (cioè ).
Soluzione
Servono 4 stati: (iniziale), (letto il primo
0), (finale: letto01all’inizio, accetta qualsiasi seguito), e (stato pozzo per le stringhe che iniziano con1o con00).stateDiagram-v2 direction LR [*] --> q0 q0 --> q1 : 0 q0 --> qP : 1 q1 --> q2 : 1 q1 --> qP : 0 q2 --> q2 : 0, 1 qP --> qP : 0, 1 q2 --> [*] : Finale
Stato 01
Esercizio 3. Aritmetica modulare con gli automi (Intermedio)
Costruisci un DFA sull’alfabeto unario che accetti tutte e sole le stringhe la cui lunghezza è un multiplo di 3 ().
Soluzione
Basta ricordare il resto della divisione per 3 della lunghezza letta finora ():
- (iniziale e finale): .
- : .
- : .
stateDiagram-v2 direction LR [*] --> q0 q0 --> q1 : a q1 --> q2 : a q2 --> q0 : a q0 --> [*] : Finale (Resto 0)
Esercizio 4. Intermedio —Complemento di un linguaggio regolare tramite DFA
Dato un DFA che riconosce un linguaggio , come si può ottenere immediatamente un nuovo DFA che riconosca il linguaggio complemento ? Applica questa regola per ottenere dal DFA dell’Esercizio 1 l’automa che accetta tutte le stringhe che non contengono la sottostringa .
Soluzione
Poiché un DFA è completo e deterministico (ogni stringa termina in uno e un solo stato ), una stringa non appartiene a se e solo se termina in uno stato di .
Pertanto basta invertire gli stati finali con quelli non finali, mantenendo identici stati, stato iniziale e transizioni:Applicandolo all’Esercizio 1, dove e , il nuovo insieme degli stati finali diventa semplicemente:
(Nota importante: questo trucco funziona solo sui DFA completi, non direttamente sugli NFA!)
Esercizio 5. Numeri binari divisibili per 2 o per 4 (Avanzato)
Costruisci un DFA sull’alfabeto che accetti tutte le stringhe binarie non vuote che rappresentano (in base 2) un numero intero pari (divisibile per 2). Come cambia l’automa se vogliamo invece i numeri divisibili per 4?
Soluzione
In base 2 (proprio come in base 10 per la divisibilità per 10), un numero binario è pari (divisibile per 2) se e solo se la sua ultima cifra a destra è
0.
L’automa per i numeri pari ha quindi 3 stati:
- (iniziale, non finale perché la stringa deve essere non vuota);
- (finale: l’ultimo bit letto è
0);- (non finale: l’ultimo bit letto è
1).- Transizioni: per ogni stato , e .
Analogamente, un numero binario (con almeno 2 bit) è divisibile per 4 se e solo se termina con
00(oppure è la singola cifra0).
Esercizio 6. Condizione doppia: parità simultanea di 0 e di 1 (Avanzato)
Progetta la tabella di transizione di un DFA su che accetti tutte e sole le stringhe aventi un numero pari di 0 E un numero dispari di 1. (Suggerimento: usa 4 stati che combinano le due parità).
Soluzione
Creiamo 4 stati corrispondenti alle 4 combinazioni di parità :
- (iniziale, perché in ci sono zero
0e zero1, entrambi pari);- (unico stato finale: Pari
0, Dispari1);- (Dispari
0, Pari1);- (Dispari
0, Dispari1).Leggere
0cambia la prima lettera del pedice (); leggere1cambia la seconda lettera del pedice:
Stato Input 0Input 1
Provenienza del materiale
- Slide e dispensa ufficiale del corso:
C1PROG1U1L1b_Automi_a_stati_finiti.pdf(Unità 1, Lezione 1b — Automi a stati finiti deterministici, non deterministici e riconoscitori di linguaggi regolari). - Marco Anisetti, Fondamenti,
Appunti_di_fine_Unita_1.pdf, §§ 1.11–1.15. - Guida unica di studio – Fondamenti,
Guida_Unita_1_teoria_approfondimenti_per_argomento.pdf, § 3. - Appunti Avanzati di Programmazione e Algoritmi I,
AppuntiInformatica-v3.pdf, § 2.