Fonction successeur de langages rationnels

Ce chapitre traite particulièrement de la fonction successeur pour des langages rationnels. Nous avons déjà vu dans les chapitres précédents que la fonction successeur dans un langage rationnel est une fonction rationnelle mais qu’elle n’est pas nécessairement séquentielle ou co-séquentielle, à travers les exemples 56 et 57. Nous allons maintenant montrer que le résultat trouvé pour ces deux exemples est un résultat général :La preuve de ce théorème, que nous donnons dans ce chapitre, construit une union finie de transducteurs séquentiels droits réalisant la fonction suc- cesseur d’un langage L à partir d’un automate fini déterministe qui recon- naît L. En fait nous réduisons le problème de la fonction successeur à une fonction successeur restreinte aux mots dont le successeur est de même lon- gueur. Pour retrouver la fonction successeur à partir de cette restriction, il faut imaginer introduire un caractère spécial que l’on insère autant de fois que nécessaire en début de mot.Afin de montrer la co-séquentialité par morceaux des fonctions succes- seur à longueur constante, nous présentons tout d’abord des constructions particulières sur des automates et sur des transducteurs pour avoir des trans- ducteurs séquentiels – nous travaillons sur les transducteurs séquentiels sans préciser s’ils sont droits ou gauches –.

Produit synchronisé d’automates monocyles

Si L et K sont deux langages rationnels avec au plus un mot par longueur, alors la fonction α qui associe à tout mot de L le mot de K, de même longueur, si il existe, est une fonction séquentielle et co-séquentielle par morceaux.Pour ce faire nous définissons les langages rayon, qui sont les langages reconnus par des automates avec un seul cycle, appelés automates mono- cycles. Nous montrons ensuite que le produit synchronisé de deux automates monocycles réalise une fonction séquentielle par morceaux.w. L’intérêt de tels langages est que tout langage à croissance bornée est une union finie de langages rayons (folklore, cf. par exemple [43, I.8.4]). En particulier, ce qui va nous intéresser, les langages qui n’ont qu’au plus un mot par longueur sont une union fini de langages rayons.Un automate monocycle est un automate émondé avec un seul état initial, un seul état final et qui est composé d’un unique circuit et de deux chemins qui relient le circuit à l’état initial et l’état final. Un transducteur monocycle est un transducteur dont l’automate d’entrée sous-jacent est monocycle.Un automate monocycle est dit à boucle préfixe soit s’il n’a pas de circuit, soit si celui-ci passe par l’état initial. Il est dit à boucle suffixe s’il n’a pas de circuit ou bien si celui-ci passe par l’état final.

 La seule source possible de non déterminisme dans un auto- mate A monocycle est à partir de l’état q dont on sort de la boucle puisque c’est le seul à avoir un degré sortant de 2. Il est possible d’éliminer ce non déterminisme sur q en faisant rouler le circuit vers l’état final, c’est-à-dire :en deux états : le premier appartient au cycle mais n’est plus l’état d’entrée du cycle, le deuxième est un état intermédiaire qui n’appartient pas au cycle mais dont la transition sortante va en qComme le chemin de sortie est fini, si le non déterminisme subsiste, il suffit de refaire rouler le circuit un nombre fini de fois (dans le pire des cas, l’automate deviendra alors a boucle suffixe). La transformation est montrée sur la Figure 8.2.La transformation ci-dessus est adaptable de manière duale pour obtenirun automate monocycle co-déterministe en roulant le cycle vers l’état initial.Le degré sortant d’un état (p, q) de A ✶ B est le produit des degrés sortants des états p de A et q de B. De la définition du produit synchronisé on tire que, même si A est déterministe, le transducteur A ✶ B n’est pas séquentiel dès B a un état de degré sortant au moins 2.