Option Informatique — Un problme tir de Combinatorics on Words

▶ On fixe un alphabet A. Soit W une partie de A^{+} telle qu’aucun lment de W ne possde de facteur propre

dans W. ▶ On note P = A^{∗} \ (A^{∗}W A^{∗}) : P est donc l’ensemble des mots dont aucun facteur n’appartient W. ▶ Soit u ∈ W ; on note X_{u} = (A^{∗}u) \ (A^{∗}W A^{+}). ▶ On note L + M la runion de deux langages L et M, et ∑_{i∈I} L_{i} la runion d’une famille (L_{i})_{i∈N} de langages.

\underline{\overline{Q1}} Justifier : X_{u} est l’ensemble des mots dont u est suffixe, mais dont aucun autre facteur n’appartient W. \underline{\overline{Q2}} Soient u et v deux lments distincts de W. Montrer que X_{u} et X_{v} sont disjoints.

\underline{\overline{Q3}} tablir : \{ε\} + P A = P + ∑_{u∈W} X_{u}.

▶ Soient u et v deux lments de W. On note R_{u,v} = {t ∈ A^{+} \ (A^{∗}v) : ut ∈ A^{∗}v}. \underline{\overline{Q4}} Expliciter R_{u,v} lorsque u = abb et v = bbb. \underline{\overline{Q5}} Montrer que R_{u,v} est une partie finie de A^{+}. \underline{\overline{Q6}} Soient u et v deux lments de W. Montrer que X_{u} et X_{v}R_{v,u} sont disjoints. \underline{\overline{Q7}} Soient u, v et w trois lments de W. On suppose v ≠ w; montrer que X_{v}R_{v,u} et X_{w}R_{w,u} sont disjoints.

\underline{\overline{Q8}} Soit u ∈ W ; tablir P u = X_{u} + ∑_{v∈W} X_{v}R_{v,u}.

▶ Dans les deux dernires questions, on fixe A = {a, b} et W = {u}, o u = aba. Pour n0, on note λ_{n} = Card(P ∩A^{n}) ; λ_{n} est donc le nombre de mots de longueur n n’ayant aucun facteur gal u. On note galement μ_{n} = Card(X_{u} ∩ A^{n}).

\underline{\overline{Q9}} tablir deux relations entre les familles (λ_{n})_{n∈ℕ} et (μ_{n})_{n∈ℕ}. \underline{\overline{Q10}} En dduire une relation de rcurrence linaire vrifie par la famille (λ_{n})_{n∈ℕ}.

[COW] Compos le 27 septembre 1998