Forum Prepas.org

Soit $ \Sigma $ l'alphabet $ \{a, b\} $
On peut raisonner par récurrence sur le nombre de $ a $ dans le mot :

Soit pour tout entier $ n\ge 0 $, $ P(n):\forall w\in\Sigma^+, |w |_a=n\implies \text{ on peut effectuer un nombre fini d'opérations sur w} $

$ P(0) $ est évident, on va aussi montrer P(1) pour faciliter l'hérédité :

Soit $ w\in\Sigma^+ $ tel que $ |w|_a=1 $. On peut montrer que l'on peut effectuer au plus une opération par $ b $ dans le mot $ w $ de départ.
En effet, si un b est à gauche de la lettre a, alors on pourra jamais l'utiliser dans une opération car lors d'une opération, on peut pas déplacer un a vers la gauche.
De plus, une fois qu'on effectue une opération avec un $ b $, les 2 b se retrouvent à gauche du a et on ne pourra plus jamais les utiliser. Donc on peut effectuer qu'un nombre fini d'opérations (car le nombre de b est aussi fini) d'où P(1).

Maintenant, soit $ n\in\mathbb{N}^* $ tel que P(n), montrons $ P(n+1) $.

Soit $ w\in\Sigma^+ $ tel que $ |w|_a=n+1 $.
Considérons le a le plus à gauche. D'après ce qu'on a vu en montrant P(1), les opérations que l'on effectue sur a n'ont pas d'influence sur les opérations qu'on effectue sur les autres a.
En effet, si on effectue une opération sur le a le plus à gauche, alors le b avec lequel on effectue l'opération est à gauche de tous les autres a donc il ne pouvait etre utilisé que par le premier a.

Ainsi, on peut effectuer d'abord toutes les opérations sur tous les a sauf le premier. On applique P(n) sur le sous-mot qui commence après le premier a, il y a un nombre fini d'opérations qui peuvent être effectué, donc le mot résultant des opérations est aussi fini.
Ainsi, on peut considérer le sous-mot qui va du début jusqu'au second a. En effet, le reste du mot va rester fixe vu qu'on ne peut plus effectuer d'opérations.

On applique donc P(1) sur ce sous-mot pour montrer P(n+1) ce qui conclut.