Problème — La grammaire de balisage du programme, de bout en bout

1. La non-ambiguïté. Introduisons la hauteur $h(u)=|u{|}_a-|u{|}_b$.

Lemme. Tout $w\in L(S)$ vérifie $h(w)=0$ et tout préfixe $p$ de $w$ vérifie $h(p)\ge 0$. Tout $t\in L(T)$ vérifie $h(t)=0$, et tout préfixe propre et non vide $p$ de $t$ vérifie $h(p)\ge 1$.

Preuve du lemme, par induction mutuelle. Pour $S\to c$ : hauteur nulle partout. Pour $S\to TS$ : la concaténation de deux mots de hauteur nulle, dont les préfixes restent positifs. Pour $T\to aSb$ : le a initial monte à $1$, les préfixes de $u$ y ajoutent une quantité positive, et seul le b final redescend à $0$.

La non-ambiguïté suit. Soit $w\in L(S)$, non vide. Sa première lettre décide la règle : si c'est c, la seule règle possible est $S\to c$ et $w=c$ ; si c'est a, la seule règle possible est $S\to TS$. Il reste à montrer que la coupure entre $T$ et $S$ est unique : d'après le lemme, la partie $T$ est le préfixe de $w$ qui ramène $h$ à zéro pour la première fois, et cette position est déterminée par $w$ seul. Chaque nœud de l'arbre étant ainsi forcé, l'arbre est unique.

Le décompte machine confirme : les $9$ mots de longueur au plus $10$ ont chacun exactement un arbre d'analyse.