Automa (informatica)
Dispositivo, o suo modello in forma di macchina sequenziale, che esegue da sé stesso un particolare compito, sulla base degli stimoli od ordini ricevuti.Si definisce anche come un sistema dinamico (si evolve nel tempo), discreto (nella scansione del tempo) e invariante (il sistema si comporta alla stessa maniera indipendentemente dall’istante di tempo agisce).
In informatica teorica, si tratta del modello di una macchina a stati in grado di manipolare simboli apparentenenti ad un dato alfabeto.
| Table of contents |
|
2 Automi a Pila 3 Testi |
Gli automi a stati finiti accettori o riconoscitori 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 formate da un alfabeto finito, un insieme finito di stati tra cui si distingue uno stato iniziale ed un sottinsieme di stati detti finali ed una funzione di transizione. Tale funzione, descritta mediante una tabella o un grafo, è 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:
Tali automi sono in grado di riconoscere linguaggi regolari o lineari.
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, o alle transizioni fra stati.
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 come quella dei linguaggi liberi.Automi a Stati Finiti
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). Finche 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 sottinsieme degli stati finali.Automi con output
Automi a Pila
