Che cos'è un trasduttore di stato finito?

Question

Qualcuno può dirmi che cos'è un trasduttore di stato finito?

Ho letto the Wikipedia article e non capisco niente.

Answer 1

Un trasduttore di stato finito (FST) è un automa a stati finiti (FSA, FA) che produce output e ingresso di lettura, il che significa che è utile per l'analisi (mentre un FSA "nudo" può essere utilizzato solo per riconoscere , cioè corrispondenza del modello).

Un FST è costituito da un numero finito di stati collegati da transizioni etichettate con una coppia di input/output. L'FST inizia in uno stato di partenza designato e salta a stati diversi a seconda dell'input, mentre produce output in base alla sua tabella di transizione.

I FST sono utili in NLP e riconoscimento vocale perché hanno delle buone proprietà algebriche, in particolare possono essere combinati liberamente (formano un'algebra) in composizione, che implementa la composizione relazionale su relazioni regolari (pensate a questo come non deterministico composizione funzionale) pur restando molto compatto. Gli FST possono eseguire il parsing di lingue regolari in stringhe in tempo lineare.

Ad esempio, una volta ho implementato l'analisi morfologica come un gruppo di FST. Il mio FST principale per i verbi trasformerebbe un verbo regolare, diciamo "camminato", in "passeggiata + PASSATO". Ho anche avuto un FST per il verbo "essere", che girerebbe "è" in "essere + PRESENTE + 3 °" (terza persona), e allo stesso modo per altri verbi irregolari. Tutti gli FST sono stati combinati in un singolo utilizzando un compilatore FST, che ha prodotto un singolo FST che era molto più piccolo della somma delle sue parti e funzionava molto velocemente. Gli FST possono essere creati da una varietà di strumenti che accettano una sintassi estesa delle espressioni regolari.

Answer 2

Un trasduttore di stato finito è essenzialmente un automa a stati finiti che funziona su due (o più) nastri. Il modo più comune di pensare ai trasduttori è come una sorta di "macchina di traduzione". Leggono da uno dei nastri e scrivono sull'altro. Questo, per esempio, è un trasduttore che converte a s in b s:

a:b all'arco significa che in questa transizione il trasduttore legge a dal primo nastro e scrive b sul secondo.

Riferimento: Finite State Transducers

Answer 3

In termini più semplici possibili, comprendo che un FST è essenzialmente una "cosa" che si sposta da uno stato all'altro in base a un nastro di ingresso e scrive un'uscita diversa nastro. Un nastro è essenzialmente un insieme di input come i caratteri in una stringa.

L'intero FST è rappresentato da un insieme di stati e collegamenti tra di loro. Un collegamento è "attivato" quando la sua condizione di input è corretta e quindi fornisce successivamente il nastro regolato.

Ad esempio, diciamo che un FST inizia con il nastro abc allo stato 1. Un collegamento allo stato 2 corrisponde a a e lo cambia in b. Verrà attivato, impostare il nastro di output su solo b e passare il rimanente bc allo stato 2. Come si può vedere, ogni stato viene attivato solo se c'è un collegamento ad esso la cui condizione di input era corretta, passa l'input rimanente a lo stato successivo e scrive su un nastro di output separato. Ogni FST attraversa il nastro una volta e lo fa uscire su un altro nastro una volta.

Per avere una migliore comprensione di loro read and take a look at the diagrams in this article.