Chapitre 2, section 3 :
Démonstration du lemme de Levi

Plus formellement, la démonstration se base sur une induction sur la longueur de "tu" (|tu|).

1. Cas de base :
   1. |tu| = 0, alors |uv| = 0 donc t=u=v=w=z=ε : CQFD
   2. |tu| > 0 et t = ε : u = vw et v=z (cas a) : CQFD
   3. |tu| > 0 et v = ε : tu = w et t=z (cas b) : CQFD
2. |tu| > 0 et t ≠ ε et v ≠ ε
   1. Hypothèse d'induction : t'u=v'w, ∃ z ∈ A^* tel que (v'=t'z et u = zw) ou (t'=v'z et zu=w).
   2. Par hypothèse, |tu| > 0 et t ≠ ε donc t=xt' (x ∈ A) et tu=xt'u
   3. De plus, |tu| > 0 donc |vw| > 0 (tu=vw) et v ≠ ε donc v=yv' (y ∈ A) et vw=yv'w
   4. Comme tu=vw alors xt'u=yv'w
   5. Selon le théorème d'unicité de la décomposition en symboles de l'alphabet, comme xt'u=yv'w alors x=y et donc t'u=v'w
   6. Donc t=xt'=xv'z=vz (cas a) ou v=xv'=xt'z=tz (cas b) : CQFD