Automa (informatica): differenze tra le versioni

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 [[Processo stocastico|stocastici]].

 

Gli automi sono spesso utilizzati per descrivere [[linguaggi formali]] in [[informatica teorica]], e per questo sono chiamati accettori o riconoscitori di un linguaggio.

 

Un automa può quindi generare più linguaggi (produzione di più sequenze).

 

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.

 

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.