Grammaires algébriques (démonstration)

[sperca]

Bonjour,

Je suis actuellement entrain de lire le dragon book (un grand classique dans le domaine de la compilation) et dans un des exercices proposés je ne comprends pas l'indice pour résoudre. En fait je ne vois pas ce qu'il apporte.

L'énoncé est le suivant : Soit G la grammaire suivante :
S -> 11 | 1001 | S0 | SS

Montrer que la grammaire G engendre des nombres divisibles par 3 (en base 2).

L'indice précise qu'il faut raisonner par récurrence sur le nombre de noeuds d'un arbre d'analyse. Intuitivement j'aurais réalisé un raisonnement par induction, donc je me demande vers quelle direction mène le nombre de noeuds de l'arbre d'analyse car dans le raisonnement par induction, le nombre de noeuds n'intervient pas directement (je pense).

Quelqu'un possèderait t-il une idée et pourrait m'aiguiller ?

Merci à vous.

Sperca
-----

[inviteafa56da9]

J'écris tous mes chiffres en base trois.

Effectivement, l'induction est toute indiquée ici. Il faut d'abord montrer que tes deux cas de bases sont bien divisibles par 11 (ce qui ne devrait pas poser trop de problèmes), puis s'intéresser aux deux règles récursives. Pour la première, la question à se poser est "si j'ajoute un 0 à la fin de mon entier, quelle opération arithmétique je lui fais subir ?". Pour la deuxième règle, c'est pareil il faut se demander en quoi ça consiste : tu as deux entier m et n, et tu les concatènes, qu'est-ce que tu peux en déduire ?

[sperca]

Bonjour et merci pour ta réponse.

Effectivement, je voyais bien le raisonnement par induction mais ma question ne demandait pas comment faire l'induction. L'induction ne me semble pas difficile, les cas de base sont tous deux divisibles par 3. Ensuite par induction, ajouter un 0 à un nombre divisible par 3 ne fait que le multiplier par deux donc il reste divisible par 3 (2*3k). Pour la concaténation de deux nombres divisibles par 3, par exemple a et b. On effectue un décalage de bits sur a de la taille de b soit 2^|b|, ce qui nous donne quelque chose comme a * 2^|b| + b où a et b sont aussi divisibles par 3, on factorise et le tour est joué (une rédaction correcte en revanche me pose plus de soucis).

Ce qui me troublait, était l'indice donné pour résoudre l'exercice : le nombre de noeuds de l'arbre d'analyse donc je ne me sers pas.

Voilà.

Merci à toi (si tu pouvais me conseiller sur la rédaction de l'induction ).

Bye

[inviteafa56da9]

Tu peux, pour rédiger correctement ton induction, te baser justement sur le nombre de nœuds d'un arbre d'analyse (comme ça c'est une rédaction propre, et en plus tu utilises l'indice !). Ça pourrait donner quelque chose comme ça :

Hypothèse de récurrence H_N : pour toute chaîne binaire x engendrée par G dont un arbre d'analyse possède moins de N nœuds, l'entier n représenté par x en binaire est divisible par 3.

H_1 : Si N=1, alors on a forcément x=11 ou x=1001, donc n=3 ou 9, donc n est divisible par 3.

Supposons que H_k est vraie pour k entre 1 et N-1, et soit x engendrée par G dont l'arbre d'analyse a N nœuds. La racine de l'arbre a deux fils, correspondant aux deux derniers cas de G. Les sous-arbres droits et gauches ont au plus N-1 nœuds chacuns, donc on peut leur appliquer l'hypothèse de récurrence. Soit x_1 et x_2 les deux chaînes engendrées par les sous-arbres.
Si la racine de l'arbre correspond à l'application de la règle 3, alors x_2=0, et donc x=concat(x_1,"0"), c'est-à-dire que n=2*n_1 où n_1 est l'entier représenté par x_1. Par hypothèse, n_1=3*m pour un certain entier m, donc n=3*(2*m) est divisible par 3.
Si la racine correspond à l'application de la règle 4, alors x=concat(x_1,x_2). Donc n = n_1*2^{|x_2|} + n_2 (avec n_1,n_2 les entiers représentés respectivement par x_1 et x_2 et |x_2| la longueur de x_2). Or par hypothèse de récurrence, n_1 = 3*m_1 et n_2 = 3*m_2 pour deux entiers m_1 et m_2, alors n = 3*( m_1*2^{|x_2|} + m_2 ). Et donc n est divisible par 3.

Le principe de récurrence permet de conclure que H_N est vraie pour tout N, c'est-à-dire que pour tout x générée par G, l'entier n représenté par x est divisible par 3.

[A voir en vidéo sur Futura]

[inviteafa56da9]

N.B.: C'est une idée de rédaction, pas forcément la rédaction parfaite ! Il y a une chose que tu peux plus détailler peut-être (mais ça dépend bcp de ton niveau d'études), c'est le fait que n = n_1*2^{|x_2|} + n_2. Si tu veux plus le faire, l'idée est la suivante : une chaîne binaire w=w_K w_{K-1} ... w_0 représente l'entier w_0 + 2*w_1 + ... + 2^K w_K. La chaîne w = concat(u,v) est définie par w_i = v_i si i < L_v où L_v est la longueur de v, et w_i = u_{i-L_v} sinon. Donc l'entier n représenté par w est égal à :
w_0 + 2*w_1 + ... + 2^(L_v-1) w_{L_v-1} + 2^(L_v) w_{L_v} + ... + 2^(L_u+L_v-1) w_{L_u+L_v-1}
= ( v_0 + ... + 2^(L_v-1) v_{L_v-1} ) + ( 2^(L_v) u_0 + ... + 2^(L_u+L_v-1) u_{L_u-1} )
= n_v + 2^(L_v) ( u_0 + ... + 2^(L_u-1) u_{L_u-1} )
= n_v + 2^(L_v) n_u
où n_u et n_v sont les entiers représentés par u et v.

[EDIT] Désolé j'ai un peu changé mes notations au fur et à mesure, |x| devenant L_x par exemple. Evite de le faire dans une vraie rédaction !