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 [CDG07]. 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 para- graphe 7.2 est consacré à la description d’un procédé qui permet d’obtenir une équation fonc- tionnelle de point fixe pour la série génératrice dénombrant les structures arborescentes engen- drées par une grammaire synchrone. Nous décrivons aussi un algorithme qui permet de calculerses premiers coefficients. Nous illustrons finalement dans le paragraphe 7.3, les notions présen- té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.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.

Notons que l’ensemble D des arbres à bourgeons ne forme pas une classe combinatoire ausens 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.bourgeons D engendré par S qui contient un bourgeon de type b. Dans ce qui suit, nous consi- dérons uniquement des grammaires synchrones émondées, et de ce fait, nous ne mentionnerons plus ce qualificatif.Ainsi, et à plus forte raison, une grammaire synchrone localement finie engendre pour tout n > 1 un nombre fini d’arbres à bourgeons de taille n ainsi qu’un nombre fini d’arbres à bourgeons ayant une évaluation donnée.Démonstration. Soit u un mot sur B. Étant donné que l’ensemble B des types de bourgeons est fini, et que d’après (7.1.14), chaque dérivation dans S augmente strictement l’évaluation de tout arbre à bourgeon sur lequel elle est appliquée, il existe un entier ℓ tel que toute dérivation qui engendre un arbre à bourgeon ayant u comme évaluation fasse moins de ℓ étapes. Maintenant, comme l’ensemble R des règles de substitution est fini, le nombre de dérivations qui engendrent des arbres à bourgeons ayant u comme évaluation est fini. Le résultat suit finalement du fait que comme B est fini, il existe un nombre fini d’évaluations de longueur n, et donc, également un nombre fini de dérivations qui engendrent des arbres à bourgeons de taille n.