Automate séquentiel

Les automates séquentiels sont des automates finis déterministes qui produisent un mot de sortie. Un tel automate peut réaliser certaines transformations comme l’addition des entiers dans une certaine représentation, la multiplication par une constante ou divers codages et décodages.

Dans un automate séquentiel, comme dans une transducteur fini, les transitions sont étiquetées par des couples formés d’une lettre d'entrée et d’un mot de sortie. De plus l’état initial est étiqueté par un mot appelé le « préfixe initial » et chaque état porte de plus un mot qui est la valeur d'une « fonction terminale ». Le mot de sortie calculé pour un mot d’entrée s’obtient en lisant l’entrée depuis l’état initial et en produisant les sorties spécifiées par les transitions ; le mot formé par ces sorties est préfixé par le préfixe initial et suffixé par le mot donné pour l’état final atteint. Si la fonction terminale n'est pas définie pour cet état, aucune sortie n'est produite. Lorsque le préfixe initial et la fonction terminale sont triviales, l'automate est un automate séquentiel pur.

La fonction réalisée par un automate séquentiel est une fonction séquentielle. C'est un cas particulier de transduction rationnelle fonctionnelle. Lorsque l'automate sous-jacent est pur, la fonction réalisée est elle-même dite pure. Un automate séquentiel pur est un transducteur fini particulier : l’automate d'entrée sous-jacent est déterministe (mais pas nécessairement complet).

Voici un exemple[1] pour éclairer le concept :

Un premier automate séquentiel.

Cet automate a deux états ; l'état initial 1 a pour préfixe initial 11 ; la fonction terminale associe à l'état 1 le mot vide et à l'état 2 le mot 00. L'automate est déterministe et incomplet. La lecture du mot ${\displaystyle abaa}$ fait passer l'automate progressivement par les états 1,2,2,1 et produit les sorties : ${\displaystyle 01,0,\varepsilon ,01}$ ; préfixée de 11, concaténées et suivies de 00, on obtient 110100100. La fonction réalisée par cet automate prend donc, pour le d'entrée ${\displaystyle abaa}$, la valeur 110100100.

On définit d'abord un automate séquentiel pur[1] : un automate séquentiel pur est un tuple

${\displaystyle {\mathcal {A}}=(Q,A,B,i,\cdot ,\star )}$

où

• ${\displaystyle Q}$ est un ensemble fini d'états,
• ${\displaystyle A}$ et ${\displaystyle B}$ sont les alphabets finis d'entrée et de sortie respectivement
• ${\displaystyle i\in Q}$ est l'état initial
• ${\displaystyle \cdot }$ est la fonction partielle de transition ${\displaystyle Q\times A\to Q}$
• ${\displaystyle \star }$ est la fonction partielle de sortie ${\displaystyle Q\times A\to B^{*}}$

Les fonctions de transition et de sortie ont le même domaine de définition ${\displaystyle D\subset Q\times A}$. On note l'absence de définition explicite d'états terminaux : un état est terminal s'il appartient au domaine de définition de la fonction de sortie

Un automate séquentiel est un tuple ${\displaystyle {\mathcal {A}}=(Q,A,B,i,\cdot ,\star ,m,\rho )}$ où ${\displaystyle (Q,A,B,i,\cdot ,\star )}$ est un automate séquentiel pur, m∈B∗ est le préfixe initial et ${\displaystyle \rho :Q\to B^{*}}$ est une fonction (partielle), appelée la fonction terminale.

La fonction de transition s’étend à ${\displaystyle Q\times A^{*}\to Q}$ en posant ${\displaystyle q\cdot \varepsilon =q}$ et, si ${\displaystyle q\cdot u}$ et ${\displaystyle (q\cdot u)\cdot a}$ sont définies,

${\displaystyle q\cdot (ua)=(q\cdot u)\cdot a}$.

La fonction de sortie s’étend à ${\displaystyle Q\times A^{*}\to B^{*}}$ en posant ${\displaystyle q\star \varepsilon =\varepsilon }$ et, si ${\displaystyle q\star u}$ et ${\displaystyle (q\cdot u)\star a}$ sont définies,

${\displaystyle q\star (ua)=(q\star u)((q\cdot u)\star a)}$.

Cette dernière formule exprime simplement que, lors d'un cheminement dans l'automate, les sorties des transitions sont concaténées à la suite.

La fonction réalisée par un automate séquentiel pur est l'application (partielle) ${\displaystyle f:A^{*}\to B^{*}}$ définie sur un mot ${\displaystyle w\in A^{*}}$ si ${\displaystyle i\cdot w}$ est définie, et qui prend la valeur

${\displaystyle f(w)=i\star w}$. La fonction réalisée par un automate séquentiel pur est l'application (partielle) ${\displaystyle f:A^{*}\to B^{*}}$

définie sur un mot ${\displaystyle w\in A^{*}}$ si ${\displaystyle i\cdot w}$ est définie, et qui prend la valeur

${\displaystyle f(w)=m(i\star w)\rho (i\cdot w)}$.

La valeur ${\displaystyle f(w)}$ est donc le mot obtenu en concaténant le préfixe initial ${\displaystyle m}$ avec le mot produit dans l'automate pur, suivi de la valeur que prend la fonction terminale sur l'état d'arrivée ${\displaystyle i\cdot w}$ (si cet état est atteint et si la fonction terminale est définie sur cet état).

La fonction réalisée par un automate séquentiel pur est appelée une fonction séquentielle pure. De même, la fonction réalisée par un automate séquentiel est appelée une fonction séquentielle.

La caractérisation des fonctions séquentielles et fonctions séquentielles pures fait appel à des notions topologiques :

• La distance géodésique[1] ou distance préfixe[4] entre deux mots u et v est le nombre ${\displaystyle d(u,v)=|u|+|v|-2|u\land v|}$ où ${\displaystyle u\land v}$ est le plus long préfixe commun de ${\displaystyle u}$ et ${\displaystyle v}$. Si on voit les mots comme étiquetant les arcs des chemins dans un arbre, le plus long préfixe commun et plus petit ancêtre commun (« least common ancestor » ou « lca » en anglais). Par exemple, pour ${\displaystyle u=ababab}$ et ${\displaystyle v=abaabba}$, on a ${\displaystyle u\land v=aba}$, donc ${\displaystyle d(u,v)=|u|+|v|-2|u\land v|=6+7-2\times 3=7}$. C'est la somme des longueurs des suffixes de ${\displaystyle u}$ et ${\displaystyle v}$ qui restent quand on leur enlève leur préfixe commun.

• Une fonction ${\displaystyle f:A^{*}\to B^{*}}$ est lipschitzienne s’il existe un ${\displaystyle K>0}$ tel que ${\displaystyle d(f(u),f(v))\leq Kd(u,v)}$ pour tout ${\displaystyle u,v\in A^{*}.}$

Un autre résultat caractérise des fonctions séquentielles parmi les fonctions rationnelles, c'est-à-dire les transductions rationnelles qui sont des fonctions. Pour cela, on dit qu'une fonction ${\displaystyle f:A^{*}\to B^{*}}$ est uniformément bornée si, pour tout entier ${\displaystyle n}$, il existe un entier ${\displaystyle N}$ tel que ${\displaystyle d(u,v)\leq n\implies d(f(u),f(v))\leq N}$ pour tous ${\displaystyle u,v}$ dans le domaine de définition de ${\displaystyle f}$.

Les fonctions séquentielles (pures) sont fermées par composition. En d'autres termes, le composé de deux fonctions séquentielles (pures) est encore une fonction séquentielle (pure).

Il est décidable si une fonction rationnelle est séquentielle (pure).

Le terme de sequential transducer apparaît déjà dans les travaux de Seymour Ginsburg sous le nom de « generalized sequential machine (gsm) »[7]. Un long chapitre est consacré à ces machines et fonctions dans le traité de Samuel Eilenberg. Marcel-Paul Schützenberger[8] appelle sous-séquentielle une fonction séquentielle, et séquentielle une fonction pure, et ne s'écarte ainsi pas des définitions de ses prédécesseurs. Jacques Sakarovitch[4] emploie la terminologie utilisée ici, reprise à sa suite aussi par Jean-Éric Pin[3] - [2].

• [Pin 2006] Jean-Eric Pin, chap. I/9 « Algorithmique et Programmation. Automates finis », dans Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs), Encyclopédie de l’informatique et des systèmes d’information, Paris, Vuibert, 2006 (ISBN 978-2711748464, HAL hal-00143940/document), p. 966-976
• [Pin 2013] Jean-Éric Pin, « Petit cours sur les fonctions séquentielles », Sainte-Marie de Ré, LIAFA, CNRS et Université Denis Diderot, mai 2013 (consulté le 3 août 2017)
• [Sakarovitch 2003] Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
• [Monmege et Schmitz 2011] Benjamin Monmege et Sylvain Schmitz, « Notes de révision : Automates et langages », Préparation à l’agrégation de mathématiques 2011–2012, LSV, ENS Cachan & CNRS, 2011 (consulté le 4 novembre 2017).
• [Schützenberger 1977] Marcel-Paul Schützenberger, « Sur une variante des fonctions séquentielles », Theoretical Computer Science, vol. 4, n^o 1,‎ 1977, p. 47-57 (ISSN 0304-3975, DOI 10.1016/0304-3975(77)90055-X, lire en ligne, consulté le 4 novembre 2017).
• [Eilenberg 1974] Samuel Eilenberg, Automata, Languages and Machines, Vol. A, Academic Press, coll. « Pure and Applied Mathematics » (n^o 58), 1974, xvi+451 (ISBN 978-0-12-234001-7).
• [Ginsburg 1966] Seymour Ginsburg, The Mathematical Theory of Context-free Languages, New York, McGraw-Hill, 1966.
• [Choffrut 1979] Christian Choffrut, « A generalization of Ginsburg and Rose's characterization of G-S-M mappings », dans ICALP 1979: Automata, Languages and Programming, Springer, coll. « Lecture Notes in Computer Science » (n^o 71), 1979 (ISSN 0302-9743, DOI 10.1007/3-540-09510-1_8), p. 88–103.
• [Ginsburg et Rose 1966] Seymour Ginsburg et Gene F. Rose, « A characterization of machine mappings », Can. J. Math., vol. 18,‎ 1966, p. 381–388 (MR 0191763).

• Automate de Mealy
• Automate fini déterministe
• Transducteur fini
• Transduction rationnelle