Emanuele Scapin - Automi di riconoscimento

Abbiamo visto che un’applicazione tipica degli automi a stati finiti è quella degli automi di riconoscimento.

Definizione 2: Un automa di riconoscimento A è una quintupla
A = < Q , S , d , qo, F >, dove
Q è un insieme di stati,
S è un alfabeto finito di simboli di ingresso,
d: Sx Q?Q è la funzione di transizione, che associa ad ogni coppia (x, q), con x Î S e q Î Q, uno stato y Î S ,
qo?Q è lo stato iniziale,
F Í Q è un insieme di stati finali

La stringa è accettata se lo stato in cui si trova l’automa dopo aver trattato l’ultimo simbolo della stringa in ingresso appartiene ad F, è rifiutata altrimenti.
In questo modo un automa di riconoscimento definisce un linguaggio L su S*.

Gli stati finali vengono indicati con una doppia circonferenza.

Il linguaggio L(A) riconosciuto dall’automa di riconoscimento A è dato da:
L(A) = {w | w?S* e d(qo,w)?F } = {w | w?S* e ?(d( qo, w))=1 }.

Si osservi che ogni parola w?S* induce nel diagramma degli stati un cammino, dallo stato iniziale qo ad uno stato q, così che il linguaggio accettato dall’automa corrisponda ai cammini che portano dallo stato iniziale in uno stato finale.

Questi tipi di automa sono utilizzati per modellizare macchine che devono raggiungere un obiettivo finale, in cui terminano, rappresentato da uno stato finale, oppure possono essere utilizzati per riconoscere se una stringa in ingresso fa parte di un particolare linguaggio.
Il riconoscimento di parole di un linguaggio è stato meglio precisato nella parte teorica di didattica ed è alla base della teoria costruttiva dei compilatori dei linguaggi di programmazione, peraltro argomento che verrà approfondito negli anni successivi da di cui la teoria degli automi è fondamentale strumento propedeutico.

Esempio di implementazione in Delphi