Quindi un automa non è altro che un sistema informatico che risponde ai nostri input (digitazioni di dati, numeri, parole, ecc........) fornendoci, come output una risposta o una azione differente a seconda della sua situazione interna.
Ad esempio un ascensore, è un automa, perchè quando noi digitiamo\scegliamo un piano lui, a seconda di dove gia si trova ( 1° piano, 2° piano, ecc......) sceglierà se salire, scendere o restare fermo.
Questi naturalmente, sono degli automi relativamente semplici dette macchine sequenziali o automi sequenziali cioè adibite a compiere un dato compito quando richiesto dall'utente.
Gli automi negli esempi precedentemente illustrati sono definiti in informatica "automi a stato finito" perchè è dotato di un insiemi limitato di stati e controllano una stringa di simboli in entrata (per la macchina sono ancora simboli, alla fine di questo processo li riconoscerà come parole)in maniera ordinata per decidere se appartiene o meno ad un alfabeto a lui noto.
questi tipi di automi sono chiamati delle quintuple perchè sono formati da 5 insiemi che sono:
(Q)=un insieme finito di stati,nel quale si distingue,
un insieme finito di simboli di input Σ,
funzione di transizione che applicata ad un simbolo e ad uno stato restituisce uno stato: δ : Σ ×Q→Q ;
uno stato iniziale (q0) scelto fra gli stati di Q ;
un insieme di stati finali F ⊆Q .
Dunque un automa a stati finiti è una quintupla: A = (Q , Σ, δ , q0, F ).
Un "automa a stati finiti" può essere espressoelencando le sue componenti e descrivendo la funzione di transizione, oppure mediante un grafo detto diagramma delle transizioni di stato o mediante una matrice
di transizione.
Dato un automa a stati finiti deterministico questo definisce un linguaggio sull’alfabeto Σ, costituito da tutte le stringhe ottenute concatenando le etichette presenti sul grafo delle transizioni sugli spigoli dei cammini che vanno dallo stato iniziale ad uno degli stati accettanti.
In altre parole il linguaggio L su Σ definito da A =(Q , Σ, δ , q0, F ) è dato da tutte le stringhe che producono una sequenza di transizioni dallo stato iniziale q0 ad uno degli stati accettanti di F .
Conˆ δ indichiamo la funzione di transizione estesa, che descrive cosa succede
(in quale stato si arriva) quando, a partire da un certo stato, l’automa elabora non
un solo simbolo, ma una stringa costituita da una sequenza di simboli.
Possiamodefinire ricorsivamente la funzione di transizione estesa (con ε indicheremo d’ora
in avanti la stringa vuota):
Un automa a stati finiti non deterministico è un automa che può trovarsi contemporaneamente in diversi stati. Anche un si definisce come una quintupla A = (Σ,Q , δ , q0, F ), dove:
• Σ è l’alfabeto finito di simboli;
• Q è l’insieme finito di stati;
• q0 ∈Q è lo stato iniziale;
• F ⊆Q è l’insieme degli stati finali accettanti;
• δ è una funzione δ : Q ×Σ → P (Q ),che a fronte di un simbolo e di uno stato
restituisce un sottoinsieme degli stati (dunque anche più di uno stato).
In parole semplici il funzionamento di un automa si può spiegare in tre veloci punti:
- 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.
Gli automi con output invece sono una classe differente da quella prima spiegata infatti, 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.
