Quindi cos'è esattamente lo stato finale di una macchina a stati finiti?

Esistono diverse varianti della definizione di una macchina a stati finiti. Quello che dai è comune nelle classi CS, in particolare per quanto riguarda i linguaggi formali e la teoria del parsing. In questo contesto, l'FSM è spesso direttamente correlato a un'espressione regolare e l'obiettivo è inserire le stringhe nell'FSM per verificare se corrispondono a un'espressione regolare.

L'insieme degli stati finali definisce quali stati sono stati finali. Non sono un tipo diverso di cose. Invece di un insieme di stati finali, puoi invece immaginare che alcuni stati siano semplicemente etichettati come stati finali. In effetti, avere un insieme di stati finali è isomorfo per aggiungere un bit a ciascuno stato che indica se è definitivo o meno.

Lo scopo di sapere quali stati sono definitivi è che una stringa è abbinata (o accettata) dalla macchina a stati se siamo in uno stato finale quando raggiungiamo la fine della stringa. Senza distinguere gli stati finali, ogni prefisso dell'input sarebbe anche "abbinato". Ad esempio, per un FSM come

1 -a-> 2 -b-> 3 ,

se 3 è uno stato finale (e gli altri no), allora (solo) corrisponderà alla stringa "ab". Se tutti sono stati finali, corrisponderà alle stringhe "", "a" e "ab".

Oltre l'analisi, molti problemi possono adattarsi a questo stampo, specialmente quando consideriamo varianti come la possibilità di flussi infiniti di input e l'aggiunta di output a stati e / o transizioni. Questa mossa consente alle FSM di fare di più che abbinare le cose, ma anche la corrispondenza può essere più potente di quanto si possa pensare (ad esempio vedere il controllo del modello). Gli esempi includono la descrizione di protocolli, la comunicazione di processi, la logica di gioco, il rilevamento di frodi, i processi aziendali e anche il controllo dei modelli, la sintesi dell'hardware e l'orchestrazione. I sistemi fisici possono anche essere parzialmente modellati da macchine a stati finiti.

Da un punto di vista tecnico uno stato finale dice semplicemente che è stato eseguito, non verrà eseguita alcuna elaborazione di input.

Da un punto pratico, ad esempio, potresti avere una macchina a stati finiti che riconosce le parole chiave, da un flusso di caratteri di input. Lo stato finale ti dirà se un particolare input (stream di caratteri) rappresenta una parola chiave riconosciuta, e in tal caso, quale.

Hai ragione nel supporre che lo stato finale possa dirti se nessuna determinata parola chiave è riconosciuta. Potrebbe esserci solo uno di questi stati finali, o potrebbero esserci più stati di "errore" (arbitrariamente, o, per indicare particolari tipi di guasti, per esempio). Gli stati finali dell'errore non sono necessariamente distinti dagli altri stati finali (per quanto riguarda l'FSM) tranne che dall'utilizzo / utilizzo dell'FSM dell'applicazione.

Indipendentemente dal fatto che un FSM abbia stati finali, ci può essere un collegamento con software e / o dispositivi esterni (ad esempio, cambiare una luce di segnalazione da rosso a verde), in modo che alcuni codici o azioni vengano attivati quando si entra in uno stato, oppure che lo stato è osservabile (può essere interrogato) tra gli input.

Non è richiesto che lo FSM abbia uno stato finale; potrebbe essere progettato per un periodo di tempo indefinito. Diciamo che un FSM riconosce parole chiave o nessuna parola chiave, ma vogliamo che continui dopo. Potremmo impostarlo in modo che gli stati che in precedenza erano descritti come definitivi ora passassero a consumare input in attesa di un separatore (come lo spazio). Alcune applicazioni dovrebbero essere collegate all'FSM osservando che ottiene determinati (ma non finali) stati per acquisire come output le parole chiave riconosciute (o errori).

Ci sono un paio di modi per vederlo. Le due risposte precedenti dicono, in sostanza, "se arriva, la macchina si ferma, poiché ha finito il suo lavoro". Questo è di gran lunga il caso d'uso più comune.

Un altro modo di guardarlo, se l'FSM è specificamente utilizzato per riconoscere una sequenza di input, è dire "Questo è un punto di arresto legale rispetto a un punto di arresto illegale". La fine dell'input viene rilevata "in un altro modo" e il manager dell'FSM cerca di vedere se si è fermato in uno degli stati di arresto legale. Se è così, tutto è buono. Se così non fosse, le luci rosse lampeggiano, le sirene si lamentano, succede qualcosa di brutto.

Secondo le definizioni dello standard UML:

FinalState is a special kind of State signifying that the enclosing Region has completed. Thus, a Transition to a FinalState represents the completion of the behaviors of the Region containing the FinalState.

Puoi immaginare di avere una macchina a stati infiniti, come ad esempio un interruttore della luce che puoi accendere e spegnere, gli eventi consentono solo la transizione tra stati non finali. Per tali esempi, lo stato finale non è rilevante.

Tuttavia, in molti casi, la macchina a stati ha una fine. Un tipico esempio è un parser, che cambierà stato (regola grammaticale riconosciuta) in base ai token ricevuti (eventi). E alcuni eventi terminano l'elaborazione del parser, come ad esempio quando incontra il parser e EOF. Quindi l'evento EOF passerebbe allo stato finale.