Automa (informatica)

In informatica teorica e in matematica discreta, un automa è un dispositivo, o un suo modello in forma di macchina sequenziale, creato per eseguire un particolare compito, che può trovarsi in diverse configurazioni più o meno complesse caratterizzate primariamente da una variabile che appartiene ad un determinato insieme di stati, e che evolve in base agli stimoli od ordini ricevuti in ingresso schematizzati da simboli appartenenti ad un determinato alfabeto.

Quando l'automa si trova in un dato stato, esso può accettare solo un sottoinsieme dei simboli del suo alfabeto. L'evoluzione di un automa parte da un particolare stato detto stato iniziale. Un sottoinsieme privilegiato dei suoi stati è detto insieme degli stati finali o marcati.

Si definisce anche come un sistema dinamico (Teoria dei sistemi) (si evolve nel tempo), discreto (nella scansione del tempo e nella descrizione del suo stato) e invariante (il sistema si comporta alla stessa maniera indipendentemente dall'istante di tempo agisce).

In genere gli automi sono deterministici, ovvero dato uno stato ed un simbolo in ingresso è possibile una sola transizione.

Automi e Linguaggi

Gli automi sono spesso utilizzati per descrivere linguaggi formali, e per questo sono chiamati accettori o riconoscitori di un linguaggio.

L'insieme dei possibili stimoli che possono essere forniti ad un automa costituisce il suo alfabeto.

Una sequenza di simboli (detto anche stringa o parola) appartiene al linguaggio se essa viene accettata dal corrispondente automa, ovvero se porta l'automa in uno stato valido, che sia lo stesso o un altro stato. Un sottoinsieme del linguaggio riconosciuto, chiamato linguaggio marcato porta l'automa dal suo stato iniziale ad uno stato finale o marcato.

A diverse classi di automi corrispondono diverse classi di linguaggi, caratterizzate da diversi livelli di complessità.

Automi a Stati Finiti

Gli automi a stati finiti sono dotati di un insieme finito di stati, scandiscono una stringa di simboli in ingresso (simbolo per simbolo) in maniera ordinata per decidere se essa appartenga o meno ad un linguaggio.

Formalmente tali automi sono delle quintuple, (Q, I, f, q0, F ), formate da un alfabeto finito dei simboli in ingresso (I), un insieme finito di stati(Q) tra cui si distingue uno stato iniziale (q0) ed un sottoinsieme di stati, detti finali (F), ed una funzione di transizione(f). Tale funzione, descritta mediante una tabella di transizione degli stati, o un multidigrafo, è definita per coppie (stato corrente, simbolo scandito) e stabilisce la transizione da compiere, ossia lo stato in cui si transita leggendo il dato simbolo.

Il funzionamento dell'automa può essere così descritto:
partendo dallo stato iniziale e dal primo simbolo della stringa in ingresso si decide in base alla funzione di transitare in un determinato stato (potrebbe anche essere lo stesso stato). Finché esiste un altro simbolo nella stringa da scandire si opera alla stessa maniera fino ad esaurire la stringa in ingresso. La stringa si dirà accettata se si giunge in uno stato appartenente al sottoinsieme degli stati finali.

Tali automi sono in grado di riconoscere i linguaggi regolari.

Automi con output

Tale classe di automi a stati finiti può associare un l'emissione di simboli appartenenti ad un altro alfabeto detto di output. Questi automi vengono chiamati macchine di Moore o di Mealy, a seconda che l'output sia associato agli stati (caso più particolare), o alle transizioni fra stati.

Operazioni con automi

Esistono operazioni che si possono effettuare su un singolo automa o su più automi. Tra le prime possiamo citare: l'accessibilità, la coaccessibilità, il trim. Tra le composizioni di automi si trova il prodotto e la composizione in parallelo.

Automi a Pila

Gli automi possono anche essere dotati di memoria supplementare (rispetto ai soli stati) ad esempio nella forma di una pila (push down automata). Tali automi sono in grado di riconoscere una classe più ampia di linguaggi rispetto agli automi a stati finiti, come quella dei linguaggi liberi.

Lo stato degli automi a pila è costituita da una pila di simboli. Solo il simbolo in cima alla pila in un dato momento è accessibile e può essere letto.

Le transizioni negli automi a pila dipendono dal simbolo in ingresso e dal simbolo in cima alla pila; una transizione può comportare il deposito di un nuovo simbolo in cima alla pila e/o l'emissione di un simbolo in uscita.

Gli automi a pila sono un sovrainsieme di quelli a stati finiti.

Macchine di Turing

Il massimo livello di complessità di un automa è raggiunto dalla macchina di Turing, modello che generalizza gli automi a pila (e a fortiori gli automi a stati finiti).

Automi con blocchi

Esistono principalmente due tipi di blocchi: deadlock e livelock. Il primo avviene quando si giunge in uno stato che non rientra fra gli stati finali e ha Γ={Φ}, ovvero in cui non ci sono uscite. Un livelock si verifica invece quando si giunge all'interno di un insieme di stati, nessuno dei quali è uno stato finale, da cui non è più possibile uscire. La presenza di questi blocchi si può individuare con algoritmi che operano sui riguardanti i digrafi sottostanti.

Automi non deterministici

Vengono studiati anche automi non deterministici, ovvero nei quali dato uno stato dell'automa ed un simbolo in ingresso è possibile più di una transizione. Questi hanno una utilità concettuale nella Teoria della complessità algoritmica.

Voci correlate

Testi

Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D.: Automi, linguaggi e calcolabilità; I ed. it.; Addison Wesley (ISBN 88-7192-154-2)

Collegamenti esterni

Linguaggi formali

Gourt Home::Gourt :: Automa (informatica)