Automa (informatica)

In teoria dei sistemi dinamici, un automa è un sistema dinamico (in quanto ha memoria del passato) discreto sia nella scansione del tempo che nella descrizione del suo stato e tempo-invariante (le sue regole di transizione non dipendono dall'istante in cui vengono applicate).

Poiché una macchina a stati e un automa sono concetti molto simili, vengono spesso usati come sinonimi; tuttavia, mentre l'automa è tradizionalmente visto come un riconoscitore di sequenze (che si limita ad accettare o rifiutare un ingresso, come ad esempio un indirizzo email o una password), la macchina a stati viene solitamente intesa come un dispositivo di controllo o trasduttore, capace di produrre uscite e azioni verso l'esterno a ogni transizione (come un semaforo dotato di pulsante o una calcolatrice con display).

Esistono strumenti come la calcolatrice dove entrambi i concetti convivono: da un lato il sistema si comporta come un automa e verifica che la stringa inserita dall'utente sia un'espressione valida, dall'altro si comporta invece come una macchina a stati, mostrando i simboli a schermo ogni volta che l'utente effettua un'azione, ossia ad ogni passaggio di stato.

L'insieme di tutti i simboli che un automa può ricevere in ingresso costituisce il suo alfabeto. In base allo stato in cui si trova, l'automa può accettare solo un sottoinsieme dei simboli del suo alfabeto. Ogni automa parte da un particolare stato, detto stato iniziale, prima di ricevere qualsiasi stimolo o ingresso. La sequenza di transizioni da uno stato all'altro costituisce la sua evoluzione. Un sottoinsieme privilegiato dei suoi stati è detto insieme degli stati finali (o marcati) che rappresentano la conclusione con successo di un'operazione.

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 dove a fronte di uno stesso stato e dello stesso simbolo in ingresso, sono possibili più transizioni diverse (caso non deterministico) oppure la transizione avviene secondo una certa probabilità (caso stocastico).

Infine, mentre un'espressione regolare descrive un linguaggio in termini dichiarativi (spiega cioè come è composto il linguaggio stesso), un automa descrive un linguaggio in termini operativi (spiega come il linguaggio può essere riconosciuto), ma le due descrizioni sono del tutto intercambiabili (teorema di Kleene).

Descrizione

Automi e linguaggi

Gli automi sono spesso utilizzati per descrivere e riconoscere i linguaggi formali nell'ambito dell'informatica teorica. Per questo motivo, vengono spesso definiti accettori o riconoscitori di linguaggi.

Fissato un automa, l'insieme non vuoto e finito dei possibili simboli che esso può ricevere in ingresso costituisce il suo alfabeto, indicato con $Σ$ .

La concatenazione arbitraria dei simboli appartenenti all'alfabeto $Σ$ genera un insieme teoricamente infinito di sequenze di lunghezza variabile, chiamate stringhe, parole o sequenze. L'insieme di tutte le stringhe possibili è indicato con $Σ^{*}$ , mentre i suoi sottoinsiemi prendono il nome di linguaggi.

Una stringa appartiene a un determinato linguaggio se e solo se viene accettata dal corrispondente automa, ovvero se, dopo aver elaborato tutti i simboli in ingresso, l'automa si trova in uno stato finale (o di accettazione).

Un sottoinsieme del linguaggio riconosciuto, chiamato linguaggio marcato, è costituito dalle stringhe che portano l'automa dallo stato iniziale a uno stato finale o marcato.

A diverse classi di automi corrispondono diverse classi di linguaggi, caratterizzate da differenti livelli di complessità e capacità espressiva.

Un automa può quindi riconoscere un linguaggio composto da più stringhe, ciascuna delle quali viene accettata secondo le regole di transizione dell'automa.

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

Automa a stati finiti

Gli automi a stati finiti sono dotati di un insieme finito di stati e scandiscono una stringa di simboli in ingresso ordinatamente un simbolo alla volta, per decidere se essa appartenga o meno a un linguaggio dato. Se ne distinguono varie tipologie.

Automa a stati finiti deterministico (DFA)

Gli automi a stati finiti deterministici (anche detti DFA) sono deterministici, ossia a ogni combinazione di stato e input corrisponde un solo stato in uscita.

Formalmente tali automi sono delle quintuple, $(Q, Σ, δ, q_{0}, F)$ , formate da un alfabeto finito dei simboli in ingresso ( $Σ$ ), un insieme finito di stati ( $Q$ ) tra cui si distingue uno stato iniziale ( $q_{0}$ ) e un sottoinsieme di stati, detti finali ( $F$ ), e una funzione di transizione ( $δ$ ). Tale funzione, descritta mediante una tabella di transizione degli stati, o un multidigrafo, è definita per coppie (stato corrente, simbolo scandito $δ : Q \times Σ \to Q$ ) e stabilisce la transizione da compiere, ossia lo stato in cui si transita leggendo il dato simbolo in un dato stato.

Si può inoltre definire una funzione di transizione estesa: $\hat{δ} : Q \times Σ^{*} \to Q$ la quale, data una stringa già formata, restituisce direttamente il risultato.

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.

Ogni linguaggio regolare ha un unico DFA minimo (a meno di rinominare gli stati), ottenibile trattando come equivalenti gli stati che si comportano allo stesso modo per qualsiasi stringa ricevano in input.

Automa a stati finiti non deterministico (NFA)

Un automa a stati finiti non deterministico (anche detto NFA) può, a partire da un dato stato e un dato simbolo, evolvere in uno tra più stati successori. In simboli: $δ : Q \times Σ \to P (Q)$ dove $P (Q)$ è l'insieme delle parti di $Q$ . Ciò significa che, dato un input e uno stato corrente, la funzione di transizione punta a un sottoinsieme degli stati $Q$ . Dato un NFA $N$ associato a un linguaggio $L (N)$ se ne può creare una controparte "deterministica" o "determinata" ossia un DFA $D$ che riconosce lo stesso linguaggio $L (D) = L (N)$ .

$ϵ$ - NFA

La variante degli $ϵ$ -NFA include gli NFA che contengono transizioni senza necessità di input, ossia: $δ : Q \times (Σ \cup {ϵ}) \to P (Q)$ . Si tratta di transizioni "automatiche". Attenzione: essendo un tipo particolare di NFA, uno stesso stato può avere più di una $ϵ$ -transizione possibile (i percorsi possono ramificare).

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

Altri progetti

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

Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica