Quel langage cette grammaire engendre-t-elle ?

1. Une énumération exhaustive de tous les mots sur $\{a,b,c\}$ jusqu'à la longueur $7$, chacun soumis à un analyseur, donne quatre mots :

$$\text{c},\text{acbc},\text{aacbcbc},\text{acbacbc}.$$

Aucun mot de longueur $0$, $2$, $3$, $5$, $6$.

2. Par induction mutuelle sur les dérivations. Notons $|w|$ la longueur.

• Si $S{\Rightarrow }^{\ast }w$ par la règle $S\to c$, alors $|w|=1\equiv 1$.
• Si $S{\Rightarrow }^{\ast }w$ par $S\to TS$, alors $w=ts$ avec $T{\Rightarrow }^{\ast }t$ et $S{\Rightarrow }^{\ast }s$.
• Si $T{\Rightarrow }^{\ast }t$, alors $t=aub$ avec $S{\Rightarrow }^{\ast }u$, donc $|t|=|u|+2\equiv 1+2\equiv 0$.

Donc $|w|=|t|+|s|\equiv 0+1\equiv 1(\mathrm{mod}3)$. Le pas d'induction est le milieu : un bloc $T$ ajoute toujours un multiple de $3$.

3. Le langage est celui des textes balisés : une suite de blocs, chaque bloc étant un contenu entre une balise ouvrante a et sa fermante b, le tout terminé par un c — et le contenu d'un bloc est lui-même un texte de ce genre. C'est exactement la structure d'un document XML ou html, avec c pour « fin de la liste » et a…b pour une paire de balises.

Pourquoi cette grammaire est l'exemple du programme. Elle exhibe l'imbrication non bornée — la seule chose qu'un automate fini ne sait pas faire — sur trois lettres et deux règles. Et l'intersection avec $a^{\ast }{b}^{\ast }$ donne $\{a^k{b}^k\}$ à un c près : c'est le langage du chapitre chap:automates, habillé.