Pour 2:
À mon avis il faut encoder la forme compressée sous forme binaire (et que l'encodage soit de taille $\lbrqacket x \rbracket$), puis on montre qu'on peut compresser à l'infini (le truc classique de la compression que compresse toujours de au moins 1 bit).
Le reste j'ai la flemme, les automates et les langages ca date de y'a trop longtemps :)
# 1 et 2
Posté par ribwund . En réponse au journal Oral d'informatique. Évalué à 2.
on prend x = 0^{n/2}1^{n/2}
Pour 2:
À mon avis il faut encoder la forme compressée sous forme binaire (et que l'encodage soit de taille $\lbrqacket x \rbracket$), puis on montre qu'on peut compresser à l'infini (le truc classique de la compression que compresse toujours de au moins 1 bit).
Le reste j'ai la flemme, les automates et les langages ca date de y'a trop longtemps :)