Résumé : On résout le problème suivant proposé par H. Straubing. Soit A un alphabet à deux lettres, n un entier positif et Aⁿ l'ensemble des mots de longueur n. Quel est le nombre maximal d'états f(n) de l'automate minimal d'une partie de Aⁿ ? Nous donnons une formule explicite pour calculer f(n) et nous montrons que

1 = limit inf_{n → ∞}nf(n)/2ⁿ ≤ limit sup_{n → ∞}nf(n)/2ⁿ = 2.

Abstract : We solve the following problem proposed by H. Straubing. Let A be a two letter alphabet, n a positive integer and Aⁿ be the set of all words of length n. What is the maximal number of states f(n) of the minimal automaton of a subset of Aⁿ ? We give an explicit formula to compute f(n) and we show that

1 = limit inf_{n → ∞}nf(n)/2ⁿ ≤ limit sup_{n → ∞}nf(n)/2ⁿ = 2.