Nota sugli Automi a Stati Finiti

La teoria degli automi e' quella che viene utilizzata nella Teoria dei Linguaggi Formali per quanto riguarda l'approccio riconoscitivo alla definizione dei linguaggi.

Le computazioni descritte dagli automi utilizzati nella teoria dei linguaggi formali sono computazioni che, preso un input, restituiscono un output di tipo YES o NO, oppure non terminano (si potrebbe far vedere che questo tipo di computazioni non sono concettualmente differenti da quelle che, preso un input, restituiscono un output su un certo codominio).

Nella teoria degli automi (come in altri modelli computazionali del resto) e' possibile restringere il modello computazionale con dei vincoli che ne limitino la potenza espressiva dal punto di vista delle computazioni rappresentabili. Abbiamo per esempio, come indicato nel testo di Ausiello et al. 2.5.3 gli Automi a Stati Finiti, gli Automi a Pila, ecc.

Per quanto riguarda gli automi a stati finiti (vedi Ausiello et al. 3.1) che riconoscono le stringhe appartenti a linguaggi regolari, e' possibile modificare leggermente questo formalismo in modo che le computazioni eseguite permettano, anziche' accettare o meno una stringa, di produrre una stringa su un opportuno insieme di caratteri di output.
E' sufficiente che, nella definizione di automa a stati finiti, si aggiunga un insieme Z di caratteri di output, si elimini la nozione di stato (o stati) finale e si faccia in modo che la funzione di transizione delta sia del tipo
delta : Sigma x K --> K x Z
Tale funzione permette ora di associare, al carattere correntemente letto ed allo stato interno attuale, lo stato successivo ed un carattere di output.
Nella rappresentazione degli automi come diagramma degli stati (o grafo di transizione, chiamato anche diagramma di flusso in alcune soluzioni degli esercizi) basta quindi indicare sopra gli archi orientati non solo il carattere letto, ma anche il carattere di output prodotto dalla transizione rappresentata dall'arco orientato.

Negli automi a stati finiti cosi' descritti si puo' vedere che le computazioni effettuate possono prendere in input anche stringhe potenzialmente infinite, restituendo passo passo, un carattere per volta, stringhe di output infinite. Questa versione degli Automi a Stati Finiti e' estremamente importante, poiche' e' con questi automi che si riesce a descrivere il comportamento dei circuiti sequenziali (che studierete nel corso di Architettura degli Elaboratori). Esistono inoltre procedure automatizzabili che, presa una specifica di funzionamento rappresentata attraverso un automa a stati finiti, permettono di sintetizzare il circuito sequenziale che realizza fisicamente tale specifica.

Prev Top Next