mot1
est égale à la composée de
mot2
(définie de façon analogue à mot1
) et de réécrit
.
Tout mot w de L peut être reconnu par G1 (par définition de L). Il
existe donc un arbre syntaxique a1 dont w est l'image par mot1
.
L'image de a1 par la fonction réécrit
est un arbre a2 de la
grammaire G2 dont l'image par mot2
est le même mot w.
Le mot w est donc aussi reconnu par G2.