imported>WeckAl: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-07-28T20:18:17Z

growthexperiments-addlink-summary-summary:3|0|0

New page

In teoria dei [[sistema dinamico|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 [[deterministico|deterministici]], ovvero dato uno stato e un simbolo in ingresso è possibile una sola transizione. Esistono comunque anche automi non deterministici, o [[Processo stocastico|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 (linguaggi formali)|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 <math>\Gamma = \{\Phi\}</math>, 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 [[digrafo (matematica)|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 ===
{{vedi anche|Automa a stati finiti}}

Gli [[automa a stati finiti|automi a stati finiti]] sono dotati di un [[insieme finito]] di stati, scandiscono una [[Stringa (linguaggi formali)|stringa]] di simboli in ingresso (simbolo per simbolo) in maniera ordinata per decidere se essa appartenga o meno a un [[Linguaggio formale|linguaggio]].

Formalmente tali automi sono delle quintuple, <math>(Q, I, f, q0, F )</math>, formate da un alfabeto finito dei simboli in ingresso (<math>I</math>), un insieme finito di stati (<math>Q</math>) tra cui si distingue uno stato iniziale (<math>q0</math>) e un sottoinsieme di stati, detti finali (<math>F</math>), e una funzione di transizione (<math>f</math>). Tale funzione, descritta mediante una [[tabella di transizione di stato|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 [[linguaggio regolare|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 ====
{{vedi anche|ω-automa}}

Gli [[Omega automa|ω-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 ===
{{vedi anche|Automa a pila}}

Gli automi possono anche essere dotati di memoria supplementare (rispetto ai soli stati) ad esempio nella forma di una [[pila (informatica)|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 [[linguaggio libero dal contesto|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 ===
{{vedi anche|Automa lineare limitato}}

Un [[automa lineare limitato]] ({{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 [[linguaggio dipendente dal contesto|linguaggi dipendenti dal contesto]] generati da grammatiche dipendenti dal contesto (o di Tipo-1 secondo la [[gerarchia di Chomsky]]).

=== Macchine di Turing ===
{{vedi anche|Macchina 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 [[Macchina che termina sempre|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 ==
*{{cita libro|Hopcroft|John E.|coautori=Motwani, Rajeev; Ullman, Jeffrey D.|Automi, linguaggi e calcolabilità|edizione=I ed. it.|editore=Addison Wesley|isbn=88-7192-154-2}}

== Voci correlate ==
* [[Informatica]]
* [[Linguaggio formale]]
* [[Multidigrafo]]
* [[Automa a stati finiti]]
* [[Macchina astratta]]

== Altri progetti ==
{{interprogetto|preposizione=sull'|wikt=automa}}

== Collegamenti esterni ==
* {{Collegamenti esterni}}
* {{FOLDOC|abstract machine|abstract machine}}

{{Linguaggi formali e grammatiche}}

{{Controllo di autorità}}
{{Portale|informatica}}

[[Categoria:Teoria dei linguaggi formali]]
[[Categoria:Teoria degli automi| ]]
[[Categoria:Modelli di calcolo]]

Automa (informatica) - Revision history

imported>WeckAl: /* growthexperiments-addlink-summary-summary:3|0|0 */