Automa (informatica): differenze tra le versioni

Revisione della struttura in paragrafi
m (rimosso template cancellato)
(Revisione della struttura in paragrafi)
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 ed un simbolo in ingresso è possibile una sola transizione. Esistono comunque anche automi non deterministici, o stocastici.
 
== Automi e linguaggi ==
Un automa può quindi generare più linguaggi (produzione di più sequenze).
 
== Automi a stati finiticon 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, 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.
 
== Classificazione degli automi ==
=== Automi a pilastati 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 ad un [[Linguaggio formale|linguaggio]].
 
Tali automi sono in grado di riconoscere i [[linguaggio regolare|linguaggi regolari]]. <!-- e [[linguaggi lineari|lineari]]. -->
 
==== Automi con output ====
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.
 
=== Automi nona deterministicipila ===
==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.
 
== 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]].
Gli automi a pila sono un sovrainsieme di quelli a stati finiti.
 
=== 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).
 
=== Automi connon deterministici 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, 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.
 
== Automi non deterministici ==
Vengono studiati anche automi non deterministici, ovvero nei quali dato uno stato dell'automa ed un simbolo in ingresso è possibile più di una transizione. Questi hanno una utilità concettuale nella [[Teoria della complessità algoritmica]].
 
3 989

contributi