Automa (informatica): differenze tra le versioni

m
Annullate le modifiche di 88.42.175.226 (discussione), riportata alla versione precedente di Paginazero
m (Annullate le modifiche di 88.42.175.226 (discussione), riportata alla versione precedente di Paginazero)
 
In genere gli automi sono '''[[deterministico|deterministici]]''', ovvero dato uno stato ed un simbolo in ingresso è possibile una sola transizione.
 
== 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 stimoli che possono essere forniti ad un automa costituisce il suo [[alfabeto]].
 
Una sequenza di simboli (detto 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 ad 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 generare più linguaggi (produzione di più sequenze).
 
== Automi a stati finiti ==
279 391

contributi