4.2 Familles simples d’arbres
135
4.2 Familles simples d’arbres
Les résultats que nous avons obtenus sur les arbres binaires sous le modèle
de Catalan s’étendent facilement aux familles simples d’arbres définies dans la
section 1.2.2. Dans cette section, F désigne une famille simple d’arbres et S
l’ensemble de symboles associé. Chaque symbole est une lettre couplée à son
arité g((). Nous supposons en outre qu’il existe au moins un symbole d’arité 0, de
sorte qu’il existe dans F des arbres finis.
4.2.1 L’exemple des expressions (mathématiques)
Nous avons présenté en section 3.1 les arbres d’expression. Prenons donc les
expressions (mathématiques) construites avec une seule variable x, les opérateurs
binaires + et ∗ (dans cette section, ∗ désigne le produit), et l’opérateur unaire
d’exponentiation exp, ce qui correspond à l’ensemble de symboles (figure 4.3)
S = {(x, 0), (exp, 1), (+, 2), (∗, 2)}.
La marque x est dite « terminale », et les expressions de ce type peuvent s’écrire
sous forme de grammaire 4 :
F = {x} | exp(F ) | F + F | F ∗ F .
Cela nous permet d’obtenir la relation suivante sur la fonction génératrice de
dénombrement notée F :
F (z) :=
e∈F
z
|e|
= z + zF (z) + 2zF
2 (z),
(4.14)
Fig. 4.3 Un arbre de taille
10, représentant l’expression
exp(x ∗ x) + (x ∗ (x + x)), où
∗ désigne le produit
4 Le signe | est utilisé ici de la manière traditionnelle en théorie des langages, pour noter le choix
entre plusieurs options.