Wikipedia

Automa a stati finiti: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Corretto nome
m grassetti
Riga 1:
Un '''automa a stati finiti''' ('''ASF''' o '''FSA''', dall'inglese Finite State Automata) o '''macchina a stati finiti''' ('''FSM''' dall'inglese Finite State Machine) è un tipo di [[automa (informatica)|automa]] che permette di descrivere con precisione e in maniera formale il comportamento di molti sistemi. Grazie alla sua semplicità e chiarezza questo modello è molto diffuso nell'[[ingegneria]] e nelle [[scienze]], soprattutto nel campo dell'[[informatica]] e della [[ricerca operativa]].
Un automa a stati finiti può essere utilizzato sia per modellare un sistema esistente che per modellare un nuovo sistema formale in grado di risolvere alcuni problemi esistenti. A quest'ultima categoria appartengono i cosiddetti '''riconoscitori di linguaggi''' e i '''traduttori'''.
La rappresentazione grafica di un ''automa a stati finiti'' è il [[grafo]].
Riga 8:
* Simboli finiti: caratteristica che determina che il numero di simboli di ingresso e di stati sia rappresentabile da un numero finito.
 
Dal punto di vista pratico, il concetto di automa a stati finiti equivale a costruire un piccolo dispositivo che mediante una testina legge una stringa di input su un nastro e la elabora, facendo uso di un meccanismo molto semplice di calcolo e di una memoria limitata. L'esame della stringa avviene un carattere alla volta attraverso precisi passi computazionali che comportano l'avanzamento della testina. In sostanza un '''ASF''' è un caso particolare di [[macchina di Turing]], utilizzato per l'elaborazione di quei linguaggi che nelle [[Gerarchia di Chomsky|Grammatiche di Chomsky]] sono definiti ''di Tipo 3'' o ''[[linguaggi regolari|Regolari]]''. Distinguiamo due tipi di automi a stati finiti: gli automi a stati finiti deterministici (ASFD) e gli automi a stati finiti non deterministici (ASFND).
 
== Automa a stati finiti deterministico ==
{{vedi anche|automa a stati finiti deterministico}}
 
Un '''ASF''' deterministico si definisce come un sistema <math>M = (I, U, S, f, g)</math>, dove
* <math>I = \{i_1, i_2, \ldots, i_n\}</math> insieme finito dei possibili simboli in ingresso
* <math>U = \{u_1, u_2, \ldots, u_m\}</math> insieme finito dei possibili simboli in uscita
Riga 23:
{{vedi anche|automa a stati finiti non deterministico}}
 
Un '''ASF''' non deterministico si definisce come un sistema <math>M = (I, U, S, f, g)</math>, dove
* <math>I = \{i_1, i_2, \ldots, i_n\}</math> insieme finito dei possibili simboli in ingresso
* <math>U = \{u_1, u_2, \ldots, u_m\}</math> insieme finito dei possibili simboli in uscita
Riga 66:
 
; Automa di Mealy e Automa di Moore
Nell''''[[automa di Moore]]''', la funzione f dipende solo dallo stato: f = S → U e dunque U(t) = f(S(t)). La macchina di Moore può essere dunque vista come una semplificazione del caso più generico, dove l'uscita dipende dallo stato e dagli ingressi. Quest'ultimo tipo di automa è detto '''[[automa di Mealy]]'''.
 
== Varie ==
Estratto da "https://it.wikipedia.org/wiki/Automa_a_stati_finiti"