Présentation

• On s'intéresse dans ce texte à l'effet sur les langages rationnels de l'opération d'extraction: dans cette opération, on fixe une partie infinie S de N* et, d'un mot donné, on ne garde que les lettres dont les indices appartiennent à S.
• Dans une première partie, on étudie le cas où S est l'ensemble des naturels pairs: l'extraction consiste donc à ne garder, d'un mot, que les lettres d'indice impair. On montre que si L est rationnel, alors le langage déduit de L par cette extraction est lui aussi rationnel. Ce résultat est généralisé ensuite aux extractions basées sur une partie de N* ultimement périodique.
• La partie programmation demande l'écriture de fonctions effectuant les opérations courantes dans l'algèbre des parties ultimement périodiques de N*: tests d'appartenance et d'inclusion, construction du complémentaire, de la réunion, de l'intersection.
• Il est possible de traiter cette partie indépendamment des autres; il suffit de lire la définition d'une partie ultimement périodique et d'admettre que l'ensemble des parties ultimement périodiques de N* est stable par union finie, intersection finie et complémentation.