0.2.3 La fonction $val_S$

Nous allons montrer comment calculer la fonction $val_S$ d'un système de numération abstrait $(\Sigma,<,L)$ au moyen d'un automate déterministe $M=(K,s,F,\Sigma,\delta)$ acceptant le langage $L$(^0.12). Pour chaque état $p\in K$ de $M$, notons $L_p=\{w\in \Sigma^*\vert p.w\in F\}$ le langage formé des mots acceptés par $M$ à partir de $p$ et $val_p$ la fonction valeur relative au système $(\Sigma,<,L_p)$ (^0.13). Rappelons que, pour tout langage $A$, on désigne par $u_n(A)$ le nombre de mots de longueur $n$ de $A$ et par $v_n(A)$ le nombre de mots de A de longueur inférieure ou égale à $n$. Nous poserons $u_n(L_p)=u(p)$ et $v_n(L_p)=v_n(p)$.

L'automate minimal du langage $a^*b^*$, représenté ci-dessous, possède trois états: $s,p$ et $q$. Les langages associés sont $L_s=a^*b^*$, $L_p=b^*$ et $L_q=\emptyset$.

Figure: L'automate minimal de $a^*b^*$.

On a donc

$$% latex2html id marker 2907\left\{ \begin{array}{cll} u_n... ...gin{array}{cll} u_n(p)&=&1\\ v_n(p)&=&n+1 \end{array}\right.$$

Proposition 0.2.1   Si $w=\alpha\beta\in L_p$, où $\vert\beta\vert>0$, alors

$$val_p(w)=val_{p.\alpha}(\beta)+v_{\vert w\vert-1}(p)-v_{\vert\bet... ...pha'<\alpha,\vert\alpha'\vert=\vert\alpha\vert}u_{\vert\beta\vert}(p.\alpha').$$

Preuve. Le nombre $val_p(w)$ est le nombre de mots de $L_p$ qui sont plus petits que $w$. Ceux-ci se répartissent en trois ensembles. Le premier contient les mots de $L_p$ qui sont plus courts que $w$. Il y en a $v_{\vert w\vert-1}(p)$. Dans le second, nous plaçons les mots de $L_p$, de longueur $\vert w\vert$ et admettant le préfixe $\alpha$. Ces mots sont ceux de la forme $\alpha\beta'$, où $\beta'$ appartient à $L_{p.\alpha}$, est de même longueur que $\beta$ mais est plus petit que lui. Il y en a $val_{p.\alpha}(\beta)-v_{\vert\beta\vert-1}(p.\alpha)$. Le dernier est constitué des mots de $L_p$, de même longueur que $w$ mais ne commençant pas par $\alpha$. Ces mots s'écrivent $\alpha'\beta'$, avec $\vert\alpha'\vert=\vert\alpha\vert,\vert\beta'\vert=\vert\beta\vert$, $\alpha'<\alpha$ et $\beta'\in L_{p.\alpha'}$.$\qed$

Illustrons cette proposition pour calculer $val_S(a^8b^7)$ sans utiliser la formule ()(^0.14). Posons $w=a^8b^7$, $\alpha=a^8$ et $\beta=b^7$. Il vient,

$$val_s(w)=val_s(b^7)+v_{14}(s)-v_{6}(s)$$

(il n'y a pas de mots $\alpha'$ de longueur $8$ plus petits que $\alpha=a^8$). Appliquons encore la proposition pour déterminer $val_s(b^7)$ en posant cette fois $\alpha=b^6$ et $\beta=b$:

$$val_s(b^7)=val_p(b)+v_6(s)-v_0(p)+\sum_{\alpha'<b^6, \vert\alpha'\vert=6}u_1(s.\alpha').$$

Les mots $\alpha'$ de longueur $6$ plus petits que $b^6$ sont $a^6$, pour lequel $u_1(s.\alpha')=2$, et les $5$ mots $a^ib^{6-i}$, $i=1,\ldots,5$, pour lesquels $u_1(s.\alpha')=1$. Au total,

$$val_S(a^8b^7)=val_p(b)+v_{14}(s)-v_0(p)+7=127.$$

.