Grammaires synchrones

Parce qu’elles permettent de décrire et d’engendrer des langages — ou ensembles de mots — les grammaires formelles [Cho56] sont des outils centraux en théorie des langages [Aut94]. Le processus emprunté par une grammaire formelle pour engendrer un mot est simple : on commence à partir d’un mot particulier, appelé axiome, auquel on applique successivement des dérivations, c’est-à-dire des substitutions de certains de ses facteurs par d’autres mots, selon un ensemble fixé de règles, dites règles de substitutions. Les mots que l’on peut obtenir ainsi forment le langage engendré par la grammaire. Plusieurs sortes de grammaires ont été introduites et étudiées : les grammaires hors contexte, les grammaires contextuelles, les grammaires sans restrictions, pour ne citer que ces exemples, qui possèdent chacune d’elles leur propre niveau de généralité, et permettent d’engendrer et de décrire certains types de langages plutôt que d’autres [HMU00]. De manière similaire, certains types de grammaires sont pensés pour engendrer non plus des mots mais plutôt des arbres enracinés. Ces grammaires sont connues sous le nom de grammaires d’arbres [CDG+07]. Pour engendrer un arbre dans une telle grammaire, on commence à partir d’un arbre particulier, également appelé axiome, auquel on applique une série de substitutions en remplaçant ses feuilles par d’autres arbres, suivant ici aussi un ensemble de règles de substitution fixé. L’objectif de ce chapitre est d’introduire un type particulier de grammaires dans le but d’engendrer des structures arborescentes selon un tout autre processus de génération. Dans nos grammaires, les substitutions doivent être synchrones : le principe est que, à chaque étape de substitution, toutes les feuilles de l’arbre sont substituées simultanément par de nouveaux arbres suivant un ensemble de règles de substitution fixé. Nous qualifions naturellement ces objets de grammaires synchrones. La motivation principale pour l’introduction de ces structures réside dans le fait que ces grammaires permettent d’engendrer des arbres tout en conservant un contrôle sur les hauteurs de chacun de ses sous-arbres. Rappelons à ce propos que la hauteur d’un arbre est la longueur du plus long chemin connectant sa racine à l’une de ses feuilles. De plus, sous certaines conditions, nous pouvons extraire, à partir d’une grammaire synchrone, une équation fonctionnelle de point fixe pour la série génératrice qui dénombre les arbres engendrés selon leur nombre de feuilles. Les résultats présentés ici sont utilisés à plusieurs reprises dans le chapitre 8, dans le but de dénombrer plusieurs types de structures arborescentes en rapport avec les arbres binaires équilibrés et le treillis de Tamari. Ce chapitre est organisé comme suit. Dans le paragraphe 7.1, nous introduisons les arbres à bourgeons, les grammaires synchrones, et le principe de substitution synchrone. Le paragraphe 7.2 est consacré à la description d’un procédé qui permet d’obtenir une équation fonctionnelle de point fixe pour la série génératrice dénombrant les structures arborescentes engendrées par une grammaire synchrone. Nous décrivons aussi un algorithme qui permet de calculer 159 Grammaires synchrones 160 Chapitre 7 — Grammaires synchrones ses premiers coefficients. Nous illustrons finalement dans le paragraphe 7.3, les notions présentées jusqu’alors en donnant trois exemples simples de grammaires synchrones : l’une engendre les arbres binaires parfaits, l’autre les arbres 2, 3-équilibrés, et la dernière, les arbres binaires équilibrés. La plupart des résultats contenus dans ce chapitre ont été publiés dans [Gir10].

Arbres à bourgeons et grammaires synchrones 

Arbres à bourgeons

Rappelons qu’un arbre plan est un arbre enraciné plongé dans le plan. Autrement dit, les sous-arbres de chacun de ses nœuds sont totalement ordonnés de gauche à droite. Définition 7.1.1. Soit B un alphabet fini et non vide. Un arbre à bourgeons sur B — ou simplement arbre à bourgeons si le contexte est clair — est un arbre plan enraciné non vide dont les nœuds sans fils, appelés bourgeons, sont étiquetés sur B. Fixons pour ce chapitre un alphabet B := {b1, . . . , bk} fini et non vide. Sauf mention contraire, tous les arbres à bourgeons considérés par la suite sont sur B. Soit D un arbre à bourgeons. Les nœuds de D sont ses sommets qui ne sont pas des bourgeons. L’ensemble des bourgeons de D est noté Brg(D). Si x est un bourgeon de D étiqueté par bi , nous dirons que x est de type bi . La frontière de D est la suite (b1, . . . , bn) de ses bourgeons, lus de la gauche vers la droite. Si b est un bourgeon de D, son évaluation ev(b) est la lettre de B qui l’étiquette. Par extension, l’évaluation ev(D) de D est l’élément de l’algèbre commutative Z[B] des polynômes sur B défini par ev(D) := Y b ∈ Brg(D) ev(b). (7.1.1) Nous avons ainsi par exemple ev z ! = z et ev   x y x   = x 2 y. (7.1.2) La taille de D est le nombre de bourgeons qu’il contient. L’ensemble des arbres à bourgeons de taille n est noté Dn, et l’ensemble de tous les arbres à bourgeons est noté D. Nous seront amenés à considérer des arbres à bourgeons étiquetés, qui sont simplement des arbres à bourgeons dont les nœuds sont étiquetés sur un alphabet A auxiliaire. Notons que l’ensemble D des arbres à bourgeons ne forme pas une classe combinatoire au sens de la définition 1.1.1 du chapitre 1. Il existe en effet pour tout n > 1 une infinité d’arbres à bourgeons de taille n. Nous pouvons par exemple construire une infinité d’arbres à bourgeons de taille 1 qui sont constitués d’une unique branche de longueur arbitrairement grande et qui possèdent un unique bourgeon.

Grammaires synchrones

Définition 7.1.2. Une grammaire synchrone est un triplet S := (B, a, R) où – B est un alphabet fini et non vide, l’alphabet des types de bourgeons; – a est un bourgeon étiqueté sur B, l’axiome de S ; – R ⊆ B × D est un ensemble fini tel que pour tout b ∈ B, il existe au moins un arbre à bourgeons D tel que (b, D) ∈ R. C’est l’ensemble des règles de substitution de S. § 7.1 — Arbres à bourgeons et grammaires synchrones 161 Soit S := (B, a, R) une grammaire synchrone. Par souci de lisibilité, nous allons utiliser la notation suivante pour les règles de substitution. Si (b, D) est une règle de substitution de S, nous la notons b 7−→S D ou simplement b 7−→ D si le contexte est fixé. De plus, par souci de concision, un ensemble de règles de substitution de la forme b 7−→S D1, . . ., b 7−→S Dn sera noté b 7−→S D1 + · · · + Dn. (7.1.3) Dérivations et langages Définition 7.1.3. Soit S := (B, a, R) une grammaire synchrone et D0 un arbre à bourgeons de frontière (b1, . . . , bn) où ev(bi) = bi pour tout i ∈ [n]. L’arbre à bourgeons D1 est dérivable depuis D0 dans S s’il existe dans R des règles de substitution b1 7−→ T1, . . ., bn 7−→ Tn telles que, en substituant simultanément les bourgeons bi de D0 par la racine de Ti pour tout i ∈ [n], on obtient D1. Ceci est noté D0 S −→ D1. Définition 7.1.4. Un arbre à bourgeons D est engendré par une grammaire synchrone S := (B, a, R) s’il existe une suite (D1, . . . , Dℓ−1) d’arbres à bourgeons telle que a S −→ D1 S −→ · · · S −→ Dℓ−1 S −→ D. (7.1.4) Nous dirons de plus que D est engendré par une dérivation de ℓ étapes et que (7.1.4) constitue une dérivation de ℓ étapes. Nous dirons aussi dans ce cas que D est engendré par S. La grammaire synchrone S est émondée si pour tout b ∈ B, il existe au moins un arbre à bourgeons D engendré par S qui contient un bourgeon de type b. Dans ce qui suit, nous considérons uniquement des grammaires synchrones émondées, et de ce fait, nous ne mentionnerons plus ce qualificatif. Définition 7.1.5. Soit S := (B, a, R) une grammaire synchrone. Le langage de S d’ordre ℓ est l’élément de Vect(D), l’espace vectoriel sur l’ensemble des arbres à bourgeons, défini par L (ℓ) S := X a S−→D1 S−→··· S−→Dℓ Dℓ. (7.1.5) Par définition, le coefficient d’un arbre à bourgeons D dans L (ℓ) S témoigne du nombre de façons d’engendrer D par des dérivations de ℓ étapes. Par extension, nous appelons langage de S l’ensemble LS des arbres à bourgeons engendrés par S. Graphes de génération Définition 7.1.6. Le graphe de génération d’ordre ℓ d’une grammaire synchrone S est le graphe orienté G (ℓ) S := (V, E) défini par V := [ 06i6ℓ n D : D apparaît dans L (i) S o , (7.1.6) et E := n (D0, D1) ∈ V 2 : D0 S −→ D1 o . (7.1.7) Le graphe de génération de S est le graphe GS ainsi défini, avec V := LS. Le graphe GS est potentiellement infini. Les graphes G (ℓ) S et GS possèdent exactement une source, l’axiome a.