Systèmes de numération abstraits et fonctions rationnelles

Systèmes de numération abstraits

Dans cette section nous définissons plus formellement les systèmes de numération abstraits et la fonction successeur.

Définition

Soit A un alphabet muni d’un ordre total <. L’ordre radiciel ≺ sur A∗ est défini par : 1 u ≺ v si  soit |u| < |v| , ou |u| = |v| , u = w a u′ , v = w b v′ et a < b . C’est-à-dire que l’ordre radiciel – également appelé ordre militaire – est l’ordre sur les mots de A∗ qui prend tout d’abord en compte la longueur du mot puis l’ordre lexicographique. Définition 30 ([30]). Un système de numération abstrait (ou SNA) est un triplet S = (L, A, <) où A est un alphabet muni d’un ordre total < et L est un langage infini de A∗ . Le système S permet une bijection entre N et L en associant à tout entier n le (n + 1)-ième mot de L dans l’ordre radiciel sur A∗ donné par <. La représentation de n est notée hniS et, inversement, la valeur d’un mot w de L est notée πS (w). Nous avons donc : hπS (w)iS = w et πS (hniS ) = n . Dans la plupart des cas, l’alphabet A et l’ordre < sur A sont fixés et il est possible de parler, par simplification, du SNA défini par le langage L et les notations peuvent être simplifiées en hniL et πL (w). Si L est un langage rationnel de A∗ , alors le système défini naturellement par L, S = (L, A, <), est dit rationnel. Exemple 54. Soit A = {a, b} , avec a < b et soit L1 le langage des mots avec un nombre pair de b L1 = {w ∈ {a, b} ∗ | |w|b ≡ 0 mod 2} . Le langage L1 est reconnu par l’automate déterministe de la Figure 6.1 : b b a a Figure 6.1 – Un automate déterministe reconnaissant les mots avec un nombre pair de b La suite des représentations des entiers dans le système de numération abstrait défini par L1 est : {ε, a, aa, bb, aaa, abb, bab, . . .} et, par exemple, h18iL1 = a a b a b and πL1 (b b a b b) = 29 . Il est également possible de décrire le langage L1 par l’arbre de la Figure 6.2 où les mots de L1, jusqu’à la longueur 3, sont entourés. 

Enumération

Pour la suite, ce qui nous intéressera particulièrement, c’est l’énumération radicielle d’un langage rationnel, c’est-à-dire la suite des représentations des entiers dans le système de numération abstrait défini par ce langage. En particulier nous étudions la fonction successeur d’un langage L. Définition 31. La fonction successeur d’un langage L sur l’alphabet A, notée SuccL, est la fonction de L dans L qui associe au mot u ∈ L le mot v tel que v soit le plus petit mot de L plus grand que u pour l’ordre radiciel. Il résulte de cette définition que le successeur du mot u de L est le mot dont la valeur dans le système de numération abstrait défini par L est l’entier suivant : πL (SuccL(u)) = πL (u) + 1 . Exemple 55 (Ex. 54 cont.). La fonction successeur apparaît naturellement sur l’arbre des représentations : le successeur d’un mot est le suivant en lisant l’arbre de gauche à droite puis de haut en bas. Par exemple : SuccL1 (aa) = bb, SuccL1 (abb) = bab et SuccL1 (bb) = aaa. 

Relations rationnelles

La fonction successeur d’un système de numération abstrait défini par un langage rationnel L est une fonction de L dans L. En fait c’est même une fonction rationnelle, c’est-à-dire que c’est une fonction réalisable par un transducteur fini. Nous donnons dans cette section toutes les définitions de ces notions, et certains résultats classiques qui nous seront utiles par la suite. Le lecteur pourra se référer à [43], par exemple, pour les énoncés et les preuves de cette section.

Relations et fonctions rationnelles

Définition 32. Une relation α de A∗ dans B∗ est dite rationnelle si son graphe est une partie rationnelle de A∗ × B∗ . L’image d’un élément u de A∗ par une relations α de A∗ dans B∗ est l’ensemble des éléments v de B∗ tels que (u, v) soit dans le graphe de α. Définition 33. Une relation rationnelle telle que l’image de tout mot a au plus un élément est appelée fonction rationnelle.