On peut y arriver sans se poser trop de questions. La
modification porte sur le regroupement de (a)a en E (au
lieu de a(a)). Les deux étages supérieurs de la pyramide sont
modifiés.
Il n'est pas sans intérêt de faire se recouvrir les deux pyramides.
La condition demandée est S (symbole de départ) apparaît au sommet
de la pyramide.
On peut justifier chaque décoration directement, ou plus subtilement à
l'aide d'une décomposition de l'intervalle [i…i+j[ en un
premier sous-intervalle [i…k[ complété par un second
[i+k…i+k+(j−k)[, où
B apparaît sur le sommet (k,i), C apparaît sur le
sommet (j−k,i+k) et A → B C est une production de la grammaire.
Plus graphiquement, pour décorer un sommet donné on décompose la
(sous-)pyramide définie par ce sommet en deux sous-pyramides qui
couvre complètement sa base. On reconstitue ainsi un arbre de
dérivation à partir de ses deux sous-arbres.
Une reconstitution possible du sommet est indiquée, il en existe une
autre qui regroupe la première sous-pyramide de la troisième ligne et
la dernière de la deuxième ligne, selon la production
S → S Em.
La base de la pyramide est de longueur ℓ.
On commence par calculer les m1,i (avec 0 ≤ i < ℓ).
m1,i = { A, A → ci ∈ G }
Où ci est le i-ème caractère de α.
En on peut ensuite calculer les lignes de la base vers le
sommet :