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 e 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 a un automa costituisce il suo alfabeto.

Una sequenza di simboli (detta 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 a 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 $\Gamma =\{\Phi \}$, 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 o uno stato di blocco, 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. Quest'ultima è particolarmente utile quando si vuole costruire il modello di un sistema molto complesso andando a combinare le sue singole parti.

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 a 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$) e un sottoinsieme di stati, detti finali ($F$), e 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 a 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 a un altro alfabeto detto di output. Questi automi vengono chiamati macchina di Moore o macchina di Mealy, a seconda che l'output sia associato agli stati (caso più particolare), o alle transizioni fra stati.

ω-automi

Gli ω-automi sono particolari automi a stati finiti che accettano input di lunghezza infinita. Sono un'astrazione particolarmente utile nel campo dei metodi formali, in particolare per le tecniche model checking. Un noto esempio di ω-automa è l'automa di Büchi.

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 e 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 astratta

Altri progetti

Altri progetti

• Wikizionario
• Wikimedia Commons

• Wikizionario contiene il lemma di dizionario «automa»
• Wikimedia Commons contiene immagini o altri file sull'automa

Collegamenti esterni

• Automa, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Automa, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) Eric W. Weisstein, Abstract Machine, su MathWorld, Wolfram Research.
• (EN) Denis Howe, abstract machine, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

Controllo di autorità	Thesaurus BNCF 26063