Automa a stati finiti: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
fix uso improprio dei corsivi; rimuovo link a specifiche implementazioni (WP:RILIEVO) |
|||
Riga 1:
Un '''automa a stati finiti''' ('''ASF''' o '''FSA''', dall'[[Lingua inglese|inglese]] ''
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
== Descrizione ==
Riga 11:
* 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
== Tipologie ==
Riga 22:
* <math>U = \{u_1, u_2, \ldots, u_m\}</math> insieme finito dei possibili simboli in uscita
* <math>S = \{s_1, s_2, \ldots, s_h\}</math> insieme finito degli stati
* <math>f: I \times S \rightarrow S</math>
* <math>g: I \times S \rightarrow U</math> funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, <math>U(t) = g(I(t), S(t)) </math>
Riga 32:
* <math>U = \{u_1, u_2, \ldots, u_m\}</math> insieme finito dei possibili simboli in uscita
* <math>S = \{s_1, s_2, \ldots, s_h\}</math> insieme finito degli stati
* <math>f: I \times S \rightarrow \mathcal{P} (S)</math>
* <math>g: I \times S \rightarrow U</math> funzione delle uscite (eventualmente parziale), che collega l'uscita al valore attuale dell'ingresso e dello stato, <math>U(t) = f(S(t), I(t)) </math>
Riga 43:
[[File:Moore Machine.PNG|thumb|right|[[Diagramma di stato (informatica)|Diagramma di stato]] di una macchina di Moore]]
Possiamo rappresentare gli automi a stati finiti con una tabella (
{| border=1 cellspacing=0 cellpadding=7 style="border:0px"
!\
Riga 62:
|}
Un'altra rappresentazione molto usata è costituita dal
A queste rappresentazioni va aggiunta la funzione di uscita corrispondente. I diagrammi di stato saranno così modificati, come si può vedere per le macchine di Mealy e di Moore.
Riga 90:
{{interprogetto}}
▲{{Linguaggi formali e grammatiche}}
▲{{Elettronica digitale}}
{{portale|elettronica|informatica}}
| |||