Macchina a stati finiti (FSM) è un termine usato da programmatori, matematici, ingegneri e altri professionisti per descrivere un modello matematico per qualsiasi sistema che abbia un numero limitato di stati condizionali dell'essere. Un esempio pratico di una macchina a stati finiti è un insieme di pulsanti su un controller per videogiochi che sono collegati a un insieme specifico di azioni all'interno del gioco. Quando un utente inserisce premendo determinati pulsanti, il sistema sa di implementare le azioni che corrispondono.
La composizione di una macchina a stati finiti è costituita da quanto segue:
- Un insieme di potenziali eventi di input.
- Un insieme di probabili eventi di output che corrispondono ai potenziali eventi di input.
- Un insieme di stati attesi che il sistema può mostrare.
Una macchina a stati finiti può essere implementata tramite software o hardware per semplificare un problema complesso. All'interno di un FSM, tutti gli stati in considerazione esistono in un elenco finito e la macchina astratta può assumere solo uno di questi stati alla volta. Questo approccio consente di studiare e testare ogni scenario di input e output.
Un FSM può essere qualcosa di molto astratto, come un modello per un'azienda rappresentato da un'illustrazione, oppure può essere qualcosa di concreto, come un distributore automatico o un computer. L'elenco delle possibili combinazioni di questi elementi è limitato all'interno di una macchina a stati finiti. In alternativa, una macchina a stati può essere sfocata. Una macchina a stati fuzzy consente la possibilità di punti di dati che non sono all'interno di categorie discrete e pre-designate.
Teoria degli automi
Sebbene la parola macchina tradizionalmente include una componente fisica, in questo contesto si riferisce a un'astrazione che potrebbe assumere la forma di qualsiasi cosa, da un insieme di eventi di input, a un computer, una semplice macchina analogica o un modello teorico di un concetto astratto nella teoria degli automi. Gli automi sono una branca teorica dell'informatica e della matematica discreta che si concentra sulla logica delle macchine semplici. I tipi di modelli computazionali all'interno della teoria degli automi includono:
- Macchine a stati finiti: modelli per qualsiasi sistema con un numero limitato di stati condizionali dell'essere.
- Automi pushdown: più complicati delle macchine a stati finiti, utilizzano regioni di memoria chiamate stack per memorizzare le informazioni come parte di un modello.
- Automi delimitati lineari (LBA) - Simile a una macchina di Turing, ma i dati sono limitati a una porzione di input all'interno di un gruppo finito di input.
- Macchine di Turing: il modello matematico più complesso all'interno della teoria degli automi per testare diverse combinazioni di input per analizzare un sistema o un problema più ampio.
Transizione di stato
Quando una macchina a stati finiti passa da uno stato all'altro, viene chiamata transizione di stato. Il test della qualità di un sistema include il controllo di ogni stato e transizione di stato considerando tutti i potenziali input che potrebbero essere inseriti. In alcuni casi, la macchina a stati finiti viene configurata utilizzando un linguaggio di programmazione e vengono eseguite le funzioni di transizione di stato. Inoltre, l'intelligenza artificiale può essere utilizzata per raccogliere dati sui sistemi con riconoscimento di pattern e modelli automatizzati.
Per problemi più semplici, le stesse informazioni possono essere visualizzate in tabelle, matrici, illustrazioni e diagrammi di flusso, ma le macchine a stati finiti consentono ai ricercatori di modellare scenari più ampi e complicati. I diagrammi della macchina a stati finiti mostrano il flusso della logica tra le combinazioni di input e output che possono apparire all'interno di una macchina specifica.