Qu'est-ce qu'un transducteur à état fini ?

Question

Quelqu'un peut-il me dire ce qu'est un transducteur à état fini ?

J'ai lu l'article de Wikipedia et ne comprennent rien.

Answer 1

Un transducteur d'état fini (FST) est un automate d'état fini (FSA, FA) qui produit une sortie aussi bien qu'il lit une entrée, ce qui signifie qu'il est utile pour l'analyse syntaxique (alors qu'un FSA "nu" ne peut être utilisé que pour la reconnaissance, c'est-à-dire la correspondance de motifs).

Une TSF est constituée d'un nombre fini d'états qui sont reliés par des transitions étiquetées avec une paire d'entrée/sortie. La TSF commence dans un état de départ désigné et passe à différents états en fonction de l'entrée, tout en produisant une sortie conformément à sa table de transition.

Les TSF sont utiles en TAL et en reconnaissance vocale parce qu'elles ont de belles propriétés algébriques, notamment le fait qu'elles peuvent être librement combinées (former une algèbre) sous composition, qui met en œuvre la composition relationnelle sur des relations régulières (pensez à cela comme à la composition de fonctions non déterministes) tout en restant très compactes. Les TSF peuvent effectuer l'analyse syntaxique de langages réguliers en chaînes de caractères en temps linéaire.

Par exemple, j'ai implémenté une fois l'analyse morphologique sous la forme d'un ensemble de TSF. Ma TSF principale pour les verbes transformait un verbe ordinaire, par exemple "marchait", en "marche+PAST". J'avais aussi une TSF pour le verbe "être", qui transformait "est" en "être+PRESENT+3ème" (3ème personne). (3ème personne), et de même pour les autres verbes irréguliers. Toutes les TSF ont été combinées en une seule à l'aide d'un compilateur de TSF, qui a produit une TSF unique beaucoup plus petite que la somme de ses parties et fonctionnant très rapidement. Les TSF peuvent être construites par une variété d'outils qui acceptent une syntaxe d'expression régulière étendue.

Answer 2

Un transducteur à états finis est essentiellement un automate à états finis qui fonctionne sur deux bandes (ou plus). La façon la plus courante de concevoir les transducteurs est de les considérer comme une sorte de "machine à traduire". Ils lisent à partir d'une des bandes et écrivent sur l'autre. Voici, par exemple, un transducteur qui traduit a dans b s :

a:b à l'arc signifie que dans cette transition, le transducteur lit a de la première bande et écrit b sur le second.

Référence : Transducteurs à états finis

Answer 3

En termes aussi simples que possible, je comprends qu'une TSF est essentiellement une "chose" qui passe d'un état à l'autre en fonction d'une bande d'entrée et écrit sur une bande de sortie différente. Une bande est essentiellement un ensemble d'entrées, comme les caractères d'une chaîne.

L'ensemble de la TSF est représenté par un ensemble d'états et de liens entre eux. Un lien est "activé" lorsque sa condition d'entrée est correcte et donne alors à l'état suivant la bande ajustée.

Par exemple, disons qu'une TSF commence par la bande abc à l'état 1. Un lien vers l'état 2 correspond a et le change en b . Ceci serait activé, réglerait la bande de sortie sur juste b et passer le reste bc à l'état 2. Comme vous pouvez le voir, chaque état n'est activé que s'il y a un lien avec lui dont la condition d'entrée était correcte, passe l'entrée restante à l'état suivant, et écrit sur une bande de sortie séparée. Chaque TSF traverse la bande une fois et sort sur une autre bande une fois.

Pour mieux les comprendre lisez et regardez les diagrammes dans cet article. ( lien original brisé ).

Answer 4

Réponse directe : un transducteur d'états finis n'est rien d'autre qu'un automate d'états finis, mais qui possède à la fois des mots d'entrée et de sortie. C'est en termes algébriques que cela se comprend le mieux.

Un langage, A, sur un alphabet X est un sous-ensemble de l'ensemble X* de tous les mots finis tirés de X ; c'est-à-dire A ⊆ X*. Une traduction, B, avec un alphabet d'entrée X et un alphabet de sortie Y est un sous-ensemble de B ⊆ X* × Y*. Cela peut être généralisé pour permettre trois canaux ou niveaux ou plus, par exemple C ⊆ X* × Y* × Z*, mais curieusement, le concept n'est apparemment pas abordé dans la littérature ; même si l'idée d'avoir plusieurs niveaux ou canaux apparaît partout dans les applications, comme dans les protocoles de communication multi-agents, ou dans la production musicale et vidéo, ainsi que dans la linguistique théorique.

L'ensemble X* est doté d'une algèbre, avec la concaténation de mots comme produit, et le mot vide, noté ici 1, comme identité. Il satisfait les deux axiomes :

    Associativity:  (uv)w = u(vw), for all u, v, w ∈ X*; 
    Identity:       w1 = w = 1w, for all w ∈ X*;

Ensemble, ces éléments constituent les propriétés déterminantes d'un monoïde . L'ensemble X* est un monoïde libre X* est donc le monoïde librement engendré à partir de l'ensemble X.

On peut définir le produit M × N de deux monoïdes quelconques, M et N, comme un monoïde, en prenant (1,1) comme identité et en définissant les produits comme (m,n)(m',n') = (mm',nn'), où m, m' ∈ M et n, n' ∈ N.

Le produit M × N est le résultat du jet des éléments de M et N ensemble et de l'imposition des relations mn = nm, pour m ∈ M et n ∈ N : en faisant passer chaque m ∈ M pour (m,1) ∈ M × N, et chaque n ∈ N pour (1,n) ∈ M × N ; l'identité (m,1)(1,n) = (m,n) = (1,n)(m,1) étant elle-même une mise en abyme de la relation mn = nm. Entre autres choses, cela signifie que M × N n'est (presque) jamais un monoïde libre.

En particulier, X* × Y* est décrit de manière équivalente comme le monoïde libre (X ∪ Y)*, lui-même soumis aux identités xy = yx, pour x ∈ X et y ∈ Y ... à condition que X et Y ne se recouvrent pas, X ∩ Y = ∅.

Les automates à états finis peuvent être définis sur tous monoïde. Ceci s'applique également à toutes les autres familles d'automates décrits dans la littérature classique : automates push-down, machines de Turing, etc. Lorsque l'automate est sur un monoïde produit, en particulier un monoïde de la forme X* × Y*, il s'agit d'un transducteur.

Les familles respectives sont