Automate séquentiel

En informatique théorique, et notamment en théorie des automates, un automate séquentiel est un automate fini déterministe avec sorties. C'est un cas particulier d'un transducteur fini, où l'automate des entrées est déterministe. Une sous-famille des automates séquentiels est celle des automates séquentiels dits purs, où certaines modalités de calcul sont simplifiées. Lorsque de plus les sorties sont des lettres, un automate séquentiel est un automate de Mealy. Les transductions rationnelles réalisées par les automates séquentiels sont des fonctions (partielles) appelées fonctions séquentielles.

Définition informelle

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).

Exemple

Voici un exemple 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 $abaa$ fait passer l'automate progressivement par les états 1,2,2,1 et produit les sorties : $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 $abaa$, la valeur 110100100.

Définition

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

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

où

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

Les fonctions de transition et de sortie ont le même domaine de définition $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 ${\mathcal {A}}=(Q,A,B,i,\cdot ,\star ,m,\rho )$ où $(Q,A,B,i,\cdot ,\star )$ est un automate séquentiel pur, m∈B∗ est le préfixe initial et $\rho :Q\to B^{*}$ est une fonction (partielle), appelée la fonction terminale.

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

$q\cdot (ua)=(q\cdot u)\cdot a$.

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

$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) $f:A^{*}\to B^{*}$ définie sur un mot $w\in A^{*}$ si $i\cdot w$ est définie, et qui prend la valeur

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

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

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

La valeur $f(w)$ est donc le mot obtenu en concaténant le préfixe initial $m$ avec le mot produit dans l'automate pur, suivi de la valeur que prend la fonction terminale sur l'état d'arrivée $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.

Exemples

Exemples de fonctions séquentielles pures

Morphisme

Tout morphisme peut être réalisé par un automate séquentiel pur à un seul état

Remplacer une suite d'espaces par un seul espace

Par exemple, le mot ab———a—a est transformé en ab—a—a.

Codage et décodage

Automate séquentiel de décodage d'un code préfixe.

Un codage défini par

$a\to 0,b\to 1010,c\to 100,d\to 1011,r\to 11$

comme tout morphisme, peut être réalisé par un automate séquentiel pur à un seul état. Le décodage est possible par un automate séquentiel pur si le code est préfixe, et plus précisément le décodage est une fonction séquentielle si et seulement si le code est à délai de déchiffrage fini. Ici, l'ensemble $\{0,1010,100,1011,11\}$ est bien un code préfixe et un automate séquentiel pur de décodage existe, donné sur la figure ci-contre. Pour le mot

010101101000101101010110

le décodage donne $abracadabra$

Exemples de fonctions séquentielles

Fonction +1

Une fonction qui ajoute 1 au nombre écrit en binaire retournée (bit le plus faible à gauche), par exemple

$1001\to 0101$, et aussi $1111\to 00001$.

Additionneur binaire

Automate séquentiel d'addition en binaire.

Un additionneur binaire prend en argument deux entiers naturels écrits en binaire, et produit en sortie la suite binaire qui représente la somme des deux entiers. Les nombres en arguments sont écrits comme couples de bits, donc sur l'alphabet produit $\{0,1\}\times \{0,1\}$, le plus court des deux nombres binaires est éventuellement complété par des 0 ; l'écriture se fait avec le bit de plus petit poids à gauche. Les deux états 0 et 1 de l'automate correspondent à l'absence respectivement la présence d'une retenue. Par exemple, pour $n=22=2+4+16=2^{1}+2^{2}+2^{4}$, dont l'écriture binaire est 01101 et $m=13=2^{0}+2^{2}+2^{3}=1+4+8$, dont l'écriture binaire complétée par un 0 à droite est 10110, la lecture des couples (0,1)(1,0)(1,1)(0,1)(1,0) fait passer successivement par les états 0,0,0,1,1,1; les lettres émises sont 1,1,0,0,0; la fonction de sortie fournit un 1 supplémentaire correspondant à la retenue, de sorte que le mot obtenu est 110001 qui est l'écriture binaire de $2^{0}+2^{1}+2^{5}=1+2+32=35=13+22$.

Autres exemples

Modèle chèvre chou loup

• Multiplicateur par une constante, division avec reste par une constante
• Multiplication ou division de polynômes à coefficients dans un corps fini par un autre fixe
• Analyse lexicale
• Modélisation de certains systèmes finis, comme la fameuse devinette du transport d'une chèvre, d'un chou et d'un loup.

Caractérisations des fonctions séquentielles

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

• La distance géodésique ou distance préfixe entre deux mots u et v est le nombre $d(u,v)=|u|+|v|-2|u\land v|$ où $u\land v$ est le plus long préfixe commun de $u$ et $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 $u=ababab$ et $v=abaabba$, on a $u\land v=aba$, donc $d(u,v)=|u|+|v|-2|u\land v|=6+7-2\times 3=7$. C'est la somme des longueurs des suffixes de $u$ et $v$ qui restent quand on leur enlève leur préfixe commun.

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

Théorème (Ginsburg et Rose (1966)) — Une fonction $f$ est une fonction séquentielle pure si et seulement si

1. $f$ est lipschitzienne ;
2. $f$ préserve les préfixe (si $u$ est préfixe de $v$, alors $f(u)$ est préfixe de $f(v)$ ;
3. $f^{-1}$ préserve les langages réguliers.

Théorème (Choffrut (1979)) — Une fonction $f$ dont le domaine de définition est préfixiel (fermé par préfixe) est une fonction séquentielle si et seulement si

1. $f$ est lipschitzienne ;
2. $f^{-1}$ préserve les langages réguliers.

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 $f:A^{*}\to B^{*}$ est uniformément bornée si, pour tout entier $n$, il existe un entier $N$ tel que $d(u,v)\leq n\implies d(f(u),f(v))\leq N$ pour tous $u,v$ dans le domaine de définition de $f$.

Théorème — Soit $f$ une fonction rationnelle. Les conditions suivantes sont équivalentes :

• $f$ est séquentielle ;
• $f$ est lipschitzienne ;
• $f$ est uniformément bornée.

Propriétés

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).

Note historique

Le terme de sequential transducer apparaît déjà dans les travaux de Seymour Ginsburg sous le nom de « generalized sequential machine (gsm) ». Un long chapitre est consacré à ces machines et fonctions dans le traité de Samuel Eilenberg. Marcel-Paul Schützenberger 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 emploie la terminologie utilisée ici, reprise à sa suite aussi par Jean-Éric Pin.

Bibliographie

• [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).

Articles connexes

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