\input bruno

\nopagenumbers

\titre{Option Informatique --- Un problème tiré de \emph{Combinatorics
on Words}}

\panneau
On fixe un alphabet $A$. Soit $W$ une partie de $A^+$ telle qu'aucun élément
de $W$ ne possède de facteur propre dans $W$.
\endpanneau

\panneau
On note $P = A^* \setminus (A^* W A^*)$: $P$ est donc l'ensemble des mots
dont aucun facteur n'appartient à $W$.
\endpanneau

\panneau
Soit $u \in W$; on note $X_u = (A^* u) \setminus (A^* W A^+)$.
\endpanneau

\panneau
On note $L+M$ la réunion de deux langages $L$ et $M$, et
$\displaystyle \sum_{i \in I} L_i$ la réunion d'une famille $(L_i)_{i \in N}$
de langages.
\endpanneau

\exo
Justifier: $X_u$ est l'ensemble des mots dont $u$ est suffixe, mais dont aucun
autre facteur n'appartient à $W$.
\endexo

\exo
Soient $u$ et $v$ deux éléments distincts de $W$.
Montrer que $X_u$ et $X_v$ sont disjoints.
\endexo

\exo
Établir:
$\{\varepsilon\} + PA
 = P + \sum\limits_{u \in W} X_u$.
\endexo

\panneau
Soient $u$ et $v$ deux éléments de $W$. On note
$R_{u,v} = \bigl\{ t \in A^+ \setminus (A^*v) : ut \in A^*v \bigr\}$.
\endpanneau

\exo
Expliciter $R_{u,v}$ lorsque $u=abb$ et $v=bbb$.
\endexo

\exo
Montrer que $R_{u,v}$ est une partie finie de $A^+$.
\endexo

\exo
Soient $u$ et $v$ deux éléments de $W$.
Montrer que $X_u$ et $X_v R_{v,u}$ sont disjoints.
\endexo

\exo
Soient $u$, $v$ et $w$ trois éléments de $W$.
On suppose $v \ne w$; montrer que
$X_v R_{v,u}$ et $X_w R_{w,u}$ sont disjoints.
\endexo

\exo
Soit $u \in W$; établir
$Pu = X_u + \sum\limits_{v \in W} X_v R_{v,u}$.
\endexo

\panneau
Dans les deux dernières questions, on fixe $A=\{a,b\}$ et $W=\{u\}$,
où $u=aba$.
Pour $n„0$, on note $\lambda_n=\Card(P \cap A^n)$; $\lambda_n$
est donc le nombre de mots de longueur $n$ n'ayant aucun facteur
égal à $u$.
On note également $\mu_n=\Card(X_u  \cap A^n)$.
\endpanneau

\exo
Établir deux relations entre les familles $(\lambda_n)_{n\in\N}$ et
$(\mu_n)_{n\in\N}$.
\endexo

\exo
En déduire une relation de récurrence linéaire vérifiée par
la famille $(\lambda_n)_{n\in\N}$.
\endexo

\endsignal


