| Montrer que le langage S = {am bn cm+n| m,n Î N} n'est pas régulier. |
Nous utilisons la méthode de preuve par contradiction.
Supposons que le langage S est régulier. Donc il existe un automate déterministe fini qui accepte S. Soit M le nombre d'états de cet automate.
On choisit un mot particulier w = aM bM c2M. Comme M+M = 2M et par définition du langage S, on a w Î S.
Comme |w| = 4M > M, on peut appliquer le lemme de gonflement. Ce lemme dit, qu'il existe une décomposition w = uvs avec v ¹ e et |uv| £ M, telle que tous les mots de la forme uvis appartiennent aussi au langage S. On ne sait pas quels sont les 3 morceaux u, v et s de la décomposition, mais pumping lemma garantit leur existence.
Comme |uv| £ M, les morceaux u et v sont dans les M premiers caractères du mot w et ne peuvent contenir que des a. Soient x et y ¹ 0 les nombres de lettres a dans u et v respectivement.
| uvs= | u | v | s | ||||||||||||||||
| w= | a | ... | ... | a | a | b | b | ... | b | b | c | c | c | c | ... | c | c | c | c |
| M | M | 2M | |||||||||||||||||
Donc, on a u = ax, v = ay, et, comme w = uvs, le dernier morceau ne peut être autre chose que aM-x-ybM c2M.
Le mot ``gonflé'' w¢ = uv2s est de la forme uvis et doit appartenir au langage S. Mais
|
| uvvs= | u | v | v | s | |||||||||||||||||
| w'= | a | ... | ... | a | ... | a | a | b | b | ... | b | b | c | c | c | c | ... | c | c | c | c |
| M+y | M | 2M | |||||||||||||||||||
Comme (M+y)+ M ¹ 2M et par définition du langage S, ce mot ne peut pas appartenir au même langage S. La contradiction obtenue conclue la preuve.
File translated from TEX by TTH, version 2.25.
On 29 Mar 2000, 20:15.