Problème — Les mots bien parenthésés, ou deux définitions pour une famille

Notons $o(w)$ et $f(w)$ les nombres de parenthèses ouvrantes et fermantes de $w$, et $s(w)=o(w)-f(w)$ son solde.

1. La condition est nécessaire. On prouve simultanément, par induction structurelle sur la construction de $w\in D$ :

$$(\mathcal{P})s(w)=0\text{et}s(p)\ge 0\text{ pour tout preˊfixe }p\text{ de }w.$$

Prouver les deux ensemble est indispensable : la seconde ne se déduit pas de la première.

Assertion, $w=\epsilon$. Le seul préfixe est $\epsilon$, de solde $0$.

Règle $w=\text{(}u\text{)}$. $s(w)=1+s(u)-1=0$ par hypothèse d'induction. Un préfixe de $w$ est $\epsilon$ (solde $0$), ou $\text{(}p$ avec $p$ préfixe de $u$ (solde $1+s(p)\ge 1>0$), ou $w$ entier (solde $0$). Tous positifs.

Règle $w=uv$. $s(w)=s(u)+s(v)=0$. Un préfixe de $w$ est soit un préfixe $p$ de $u$, de solde $s(p)\ge 0$, soit $uq$ avec $q$ préfixe de $v$, de solde $s(u)+s(q)=0+s(q)\ge 0$. C'est ici que $s(u)=0$ sert, et c'est pourquoi les deux propriétés voyagent ensemble.

2. Le reconnaisseur. L'invariant est la propriété $(\mathcal{P})$, lue de gauche à droite.

(* Renvoie true ssi s est bien parenthese. Complexite : Theta(|s|) en temps,
   Theta(1) en memoire. *)
let reconnait s =
  let n = String.length s in
  let rec aux i solde =
    (* INVARIANT : solde = s(s[0..i-1]), et tout prefixe deja lu a un solde >= 0 *)
    if solde < 0 then false
    else if i = n then solde = 0
    else aux (i+1) (if s.[i] = '(' then solde + 1 else solde - 1)
  in aux 0 0

Terminaison : variant $n-i$, qui décroît de $1$ à chaque appel et reste positif. Correction : l'invariant est vrai à l'entrée ($i=0$, solde $0$) ; il se conserve, le solde étant mis à jour selon la lettre lue ; à la sortie, ou bien un solde négatif a été rencontré et le mot est rejeté, ou bien $i=n$ et l'on teste $s(w)=0$. La fonction rend donc vrai exactement quand $(\mathcal{P})$ est vraie. Elle est récursive terminale : le compilateur OCaml en fait une boucle, et la mémoire reste constante.

3. La réciproque, par récurrence forte sur $|w|$. Soit $w$ de solde nul dont tous les préfixes ont un solde positif ou nul.

Si $w=\epsilon$, il est dans $D$. Sinon, $w$ commence par $\text{(}$ — sans quoi son préfixe de longueur $1$ aurait un solde $-1$. Soit $k$ le plus petit indice $>0$ tel que le préfixe $w[\mathrm{0..}k]$ ait un solde nul ; il existe, puisque $w$ entier convient. Écrivons $w=u^{\prime }v$ avec $u^{\prime }=w[\mathrm{0..}k]$.

Alors $u^{\prime }=\text{(}u\text{)}$ : la première lettre est $\text{(}$, la dernière est $\text{)}$ car le solde passe de $1$ à $0$ à cette position, et le mot $u$ intérieur a un solde nul. Ses préfixes ont un solde positif ou nul, car un préfixe $p$ de $u$ donne le préfixe $\text{(}p$ de $w$, de solde $1+s(p)\ge 1$ par minimalité de $k$ — c'est le choix du plus petit $k$ qui fait tout le travail. De même $v$, de longueur $|w|-k-1<|w|$, vérifie les deux conditions.

Par hypothèse de récurrence forte, $u\in D$ et $v\in D$ ; les deux règles donnent $\text{(}u\text{)}\in D$ puis $w=\text{(}u\text{)}v\in D$.

Vérification exhaustive. Pour $2n$ allant de $0$ à $12$, on a engendré tous les mots de $D$ et, séparément, filtré tous les mots de longueur $2n$ par le reconnaisseur. Les deux ensembles sont identiques à chaque longueur. La longueur $12$ met $4096$ mots à l'épreuve.

4. Le dénombrement, mesuré :

Ce sont les nombres de Catalan $C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$. La récurrence se lit sur la décomposition de la question 3, qui est unique : $w=\text{(}u\text{)}v$ avec $|u|=2i$ et $|v|=2(n-1-i)$, d'où

$$C_n=\sum _{i=0}^{n-1}{C}_i{C}_{n-1-i},C_0=1.$$

Les cinq mots de longueur $6$ : ((())), (()()), (())(), ()(()), ()()().

Ce que le problème a vraiment établi. Deux définitions d'apparence sans rapport — l'une constructive par des règles, l'autre déclarative par une condition sur les soldes — décrivent la même famille. C'est la situation la plus fréquente en informatique : la première dit comment fabriquer, la seconde comment vérifier, et il faut les deux. Les mêmes nombres de Catalan compteront les arbres binaires au chapitre chap:arbres — et ce n'est pas une coïncidence : la décomposition unique $w=\text{(}u\text{)}v$ est exactement la décomposition d'un arbre en sa racine, son fils gauche et son fils droit.