Fondamenti di informatica - Laurea triennale Informatica/Automi non-deterministici a stati finiti

Grammatiche regolari e automi a stati finiti possono descrivere gli stessi linguaggi regolari.

Da automi a stati finiti a grammatiche regolari

Un automa finito può esprimere una grammatica regolare. Gli stati dell’automa diventano simboli non terminali, i simboli di input diventano terminali e ogni arco dell’automa corrisponde a una produzione grammaticale. Se uno stato è accettante, si aggiunge una produzione che permette di terminare la derivazione con la stringa nulla.

Dato un automa finito, è possibile costruire una grammatica regolare che genera esattamente lo stesso linguaggio accettato dall’automa. La dimostrazione procede in due direzioni: ogni stringa accettata dall’automa può essere derivata dalla grammatica, e ogni stringa generata dalla grammatica corrisponde a un cammino dell’automa che termina in uno stato accettante.

Da grammatica regolare ad automa non-deterministico a stati finiti

Esempio di automa non deterministico a stati finiti. Il simbolo "1" da due possibili derivazioni a partire dallo stato "p"

Nel costruire un automa a partire da una grammatica regolare tuttavia emerge una difficoltà: la costruzione può produrre un diagramma in cui da uno stesso stato partono più archi con la stessa etichetta, oppure mancano alcune transizioni. Questo tipo di struttura non è un automa finito deterministico, ma un automa finito non deterministico, detto anche NFA.

Un automa finito non deterministico differisce da un automa deterministico perché, dato uno stato e un simbolo di input, il prossimo stato non è necessariamente unico. La funzione di transizione non restituisce un singolo stato, ma un insieme di stati possibili. Quindi, leggendo un simbolo, l’automa può avere più scelte oppure nessuna.

Una stringa è accettata da un automa non deterministico se esiste almeno un cammino che legge tutta la stringa partendo dallo stato iniziale e termina in uno stato accettante. Non è necessario che tutti i cammini abbiano successo: basta che ce ne sia uno valido. Se invece non esiste alcun cammino valido, oppure tutti i cammini terminano in stati non accettanti, la stringa non viene accettata.

Da ogni grammatica regolare si può costruire un automa finito non deterministico che accetta esattamente il linguaggio generato dalla grammatica. Per farlo, i simboli non terminali diventano stati, si aggiunge eventualmente un nuovo stato finale, e le produzioni della grammatica vengono trasformate in transizioni dell’automa.

In sostanza quindi le grammatiche regolari e gli automi finiti non deterministici sono strumenti equivalenti per descrivere linguaggi regolari.