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:

  1. : insieme finito e non vuoto degli stati interni dell’automa ().

  2. : alfabeto di input (insieme finito e non vuoto di simboli che l’automa può leggere sul nastro di ingresso).

  3. (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).

  4. : lo stato iniziale, ovvero lo stato in cui si trova l’automa prima di leggere il primo carattere della stringa.

  5. : 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:

  1. 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 .
  2. 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.

StatoMoneta da 10Moneta da 20
0 (iniziale)1020
102030
2030X
30 (finale)XX
XXX
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 ():

StatoInput 0Input 1Significato 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 era 1 non preceduto da 0).
  • : l’ultimo carattere letto è stato 0 (siamo a metà del pattern 01! Se ora arriva 0 restiamo in perché anche questo nuovo 0 può fare da inizio di 01; se arriva 1 completiamo 01).
  • (Finale): gli ultimi due caratteri letti sono esattamente 01. Se la stringa finisce qui, accettiamo! Se invece continua: con uno 0 torniamo in (perché il nuovo 0 potrebbe iniziare un nuovo 01), mentre con un 1 gli ultimi due caratteri diventano 11, 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

  1. 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 .
  2. Sbagliare le transizioni di “ripartenza” nel riconoscimento di sottostringhe
    Nell’Esempio 2 (stringhe che terminano con 01), molti studenti nello stato (dopo aver letto 0), se leggono un altro 0, tornano erroneamente a . In questo modo la stringa 001 verrebbe rifiutata! Se ho letto 0 e leggo un altro 0, l’ultimo carattere visto è comunque uno 0, quindi devo rimanere in .
  3. 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.

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è ).

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 ().

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 .

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?

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à).


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.