Indietro

ⓘ Automa (informatica)




Automa (informatica)
                                     

ⓘ Automa (informatica)

In teoria dei sistemi dinamici, un automa è un sistema dinamico discreto e tempo-invariante.

Quando lautoma si trova in un dato stato, esso può accettare solo un sottoinsieme dei simboli del suo alfabeto. Levoluzione 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.

                                     

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

Linsieme 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 lautoma in uno stato valido, che sia lo stesso o un altro stato. Un sottoinsieme del linguaggio riconosciuto, chiamato linguaggio marcato porta lautoma 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.

                                     

1.2. Descrizione 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 allinterno 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.

                                     

1.3. Descrizione Operazioni con automi

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

                                     

2.1. Classificazione degli automi 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 dellautoma può essere così descritto:

  • finché esiste un altro simbolo nella stringa da scandire si opera alla stessa maniera fino ad esaurire la stringa in ingresso;
  • 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;
  • 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.



                                     

2.2. Classificazione degli automi Automi con output

Tale classe di automi a stati finiti può associare lemissione 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 loutput sia associato agli stati caso più particolare, o alle transizioni fra stati.

                                     

2.3. Classificazione degli automi 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 lemissione di un simbolo in uscita.

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

                                     

2.4. Classificazione degli automi 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 dellinput. 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.

                                     

2.5. Classificazione degli automi 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.

                                     

2.6. Classificazione degli automi Automi non deterministici

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