Selon le lemme de pompage, si cette langue est régulière alors il doit exister un certain nombre p tel que pour toutes les chaînes plus longues que p dans la langue, on peut décomposer cette chaîne en x + y + z, où chacun x, y et z sont des chaînes et | y | > = 1, | x + y | < = p, et x + (y * i) + z est dans la langue pour tous les nombres entiers non négatifs i.
Observons maintenant que pour tout entier non négatif i, la chaîne "1" * i + "0" + "1" * i est dans la langue. (Autrement dit, la chaîne de i1 s suivi d'un seul 0 puis i plus 1 s)
Plus précisément, la chaîne S consistant en p1 s, suivie d'une 0 puis p plus 1 s est dans la langue. Etant donné que cette chaîne a une longueur de 2 p + 1, cette chaîne est assez longue qu'elle peut être divisée en trois cordes x, y, et z comme dans le lemme de pompage. Depuis | x + y | < = p, il faut que x et y sont tous 1 s, et le seul caractère 0 dans S est en z.Considérons maintenant la chaîne S » = x + y + y + y + z. Depuis que nous avons ajouté 2 * | y | caractères, S ' doit également avoir une longueur impaire. Mais nous avons ajouté un certain nombre de caractères 1 à gauche du seul 0 dans S, et n'a pas ajouté de caractères 1 à droite du 0. Donc S ' n'a pas de 0 comme caractère du milieu, et donc S' n'est pas dans la langue. Par conséquent, nous avons montré que le langage ne peut pas être pompé comme l'exige le lemme de pompage. Par conséquent, la langue n'est pas régulière.
@templatetypedef Je n'ai rien pu essayer jusqu'à présent. Je sais ce qu'est le lemme de pompage mais je ne sais pas comment l'appliquer à cette situation – HJGBAUM
"expression régulière n'est pas un langage régulier" - bien que ce n'est pas possible expression régulière ne peut être écrit que pour une langue régulière. L'expression régulière est une preuve que certaines langues * sont des langues * régulières. –