(Attention quand on dit que |x| c'est la taille du mot x c'est le nombre de lettres ! pas le log du nombre de lettre.)
Alors pour la question 1 vous avez déja trouvé, on avait considéré 1^n.
La question 2 c'est plus dur. En fait il faut trouver des mots pour lesquels on peut trouver la représentation la plus concise, c'est ça qui est psa évident.
On a considéré les préfixes du mot 010011000111000011110000011111... en fait, les préfixes de ce mot qui sont de taille k(k+1) pour que ça s'arrète après une séquence de 1.
A partir de ça il faut montrer que la représentation la plus concise, c'est celle à laquelle on pense naturellement, comme ça on peut exprimer \langle x\rangle avec une somme de log et d'entiers.
En minorant, on peut obtenir une inégalité sqrt(n)< c log(n), pour n=k(k+1) avec k aussi grand qu'on veut donc c'est absurde.
(mais on doit pouvoir considérer d'autres mots, il faut juste trouver des mots pour lesquels on peut minorer la taille de la représentation la plus concise...)
Indice pour la question 3, il faut utiliser le lemme de l'étoile, les mots de la forme u.v^k.w étant bien compressibles...
Pour la question 4 c'est un peu plus compliqué, on verra tout à l'heure. (Mais il faut considérer un automate qui reconnaît le langage et réfléchir avec des mots d'une taille énorme, pour les mots de petites tailles on peut prendre x=y et ajuster la constante à la fin pour que l'inégalité soit vraie.)
# Début de solution
Posté par Nénuphare Rose . En réponse au journal Oral d'informatique. Évalué à 1.
Alors pour la question 1 vous avez déja trouvé, on avait considéré 1^n.
La question 2 c'est plus dur. En fait il faut trouver des mots pour lesquels on peut trouver la représentation la plus concise, c'est ça qui est psa évident.
On a considéré les préfixes du mot 010011000111000011110000011111... en fait, les préfixes de ce mot qui sont de taille k(k+1) pour que ça s'arrète après une séquence de 1.
A partir de ça il faut montrer que la représentation la plus concise, c'est celle à laquelle on pense naturellement, comme ça on peut exprimer \langle x\rangle avec une somme de log et d'entiers.
En minorant, on peut obtenir une inégalité sqrt(n)< c log(n), pour n=k(k+1) avec k aussi grand qu'on veut donc c'est absurde.
(mais on doit pouvoir considérer d'autres mots, il faut juste trouver des mots pour lesquels on peut minorer la taille de la représentation la plus concise...)
Indice pour la question 3, il faut utiliser le lemme de l'étoile, les mots de la forme u.v^k.w étant bien compressibles...
Pour la question 4 c'est un peu plus compliqué, on verra tout à l'heure. (Mais il faut considérer un automate qui reconnaît le langage et réfléchir avec des mots d'une taille énorme, pour les mots de petites tailles on peut prendre x=y et ajuster la constante à la fin pour que l'inégalité soit vraie.)