Automa (informatica)

In teoria dei sistemi dinamici, un automa è un sistema dinamico discreto (nella scansione del tempo e nella descrizione del suo stato) e tempo-invariante (il sistema si comporta alla stessa maniera indipendentemente dall'istante di tempo in cui agisce).

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.

In genere gli automi sono deterministici, ovvero dato uno stato ed un simbolo in ingresso è possibile una sola transizione. Esistono comunque anche automi non deterministici, o stocastici.

Descrizione

Automi e linguaggi

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

L'insieme dei possibili simboli 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à.

Un automa può quindi riconoscere più linguaggi (produzione di più sequenze).

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.

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 e il complemento. Tra le composizioni di automi si trova il prodotto e la composizione in parallelo.

Classificazione degli automi

Elenchiamo una classificazione dei vari tipi di automi, elencati per capacità crescente. Una sintesi è riportata nella tabella presente nella pagina.

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 l'emissione di simboli appartenenti ad un altro alfabeto detto di output. Questi automi vengono chiamati macchine di Moore o di macchina di Mealy, a seconda che l'output sia associato agli stati (caso più particolare), o alle transizioni fra stati.

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 dal contesto.

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.

Automi lineari limitati

Un automa lineare limitato (in inglese linear bounded automata, LBA) è una particolare macchina di Turing non deterministica, nella quale la lunghezza del nastro è funzione lineare della dimensione dell'input. Questi automi sono in grado di accettare linguaggi dipendenti dal contesto generati da grammatiche dipendenti dal contesto (o di Tipo-1 secondo la gerarchia di Chomsky).

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

Un sottoassieme di macchine di Turing è costituito dalle Macchine che terminano sempre, o decider nella terminologia inglese, che sono macchine per le quali è sempre garantita la terminazione della computazione, per qualunque input.

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.

Bibliografia

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

Voci correlate

• Informatica
• Linguaggio formale
• Multidigrafo
• Automa a stati finiti
• Macchina sequenziale sincrona e asincrona
• Macchina astratta

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su automa

Collegamenti esterni

• (EN) Eric W. Weisstein, Automa, su MathWorld, Wolfram Research.

Controllo di autorità	Thesaurus BNCF 26063