Automa (informatica): differenze tra le versioni

m
Annullate le modifiche di FrescoBot (discussione), riportata alla versione precedente di Vbrm
m (Bot: i simboli corretti degli ordinali sono º e ª e modifiche minori)
m (Annullate le modifiche di FrescoBot (discussione), riportata alla versione precedente di Vbrm)
L'insieme dei possibili simboli che possono essere forniti ad un automa costituisce il suo [[alfabeto]].
 
Una sequenza di simboli (detto anche [[Stringa (linguaggi formali)|stringa]] o [[parola]]) elevoappartiene 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 ad uno stato finale o marcato.
 
A diverse classi di automi corrispondono diverse classi di linguaggi, caratterizzate da diversi livelli di complessità.
===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 ===