Résumé : On résout le problème suivant
proposé par H. Straubing. Soit A un alphabet à deux
lettres, n un entier positif et An l'ensemble des
mots de longueur n. Quel est le nombre maximal d'états
f(n) de l'automate minimal d'une partie de An ?
Nous donnons une formule explicite pour calculer f(n) et nous
montrons que
Abstract : We solve the following problem proposed by H. Straubing.
Let A be a two letter alphabet, n a positive integer and
An 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 An ? We give an explicit formula to compute
f(n) and we show that