Automa (informatica): differenze tra le versioni

Adeguamento del testo
(Revisione della struttura in paragrafi)
(Adeguamento del testo)
 
== 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 automi a pila sono un sovrainsieme di quelli a stati finiti.
 
===Automi lineari limitati===
{{vedi anche|Automa lineare limitato}}
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 [[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 ===
3 989

contributi