------------------------------------------------------------------
si L est regulier, alors il existe une constante N telle que :

pour tout mot w de taille >=N, w se décompose en xyz
     - xy de taille <=N
     - y<>epsilon

et ensuite, quel que soit k>=0, tous les xy^kz sont dans L
------------------------------------------------------------------

L1={a ^nb^n|n>=0}

Supposons L régulier, alors le lemme de l'etoile dit qu'il existe une
constante N tq ... Prenons w=a^Nb^N. Comme |W|>=N, il existe des mots
x,y,z tels que |xy|<=N, y<>epsilon, tels que pour tou k, xy^kz est
dans L.

Comme |xy|<N, forcément x et y ne contiennent que des a. donc 
      x=a^c1,   y=a^c2 avec c1+c2 <=N et c2 >0
  ce qui implique  z= a^c3b^N, avec c1+c2+c3 = N

Considérons maintenant xy^2z = a^(c1+2c2+c3)b^N
	    -- d'après nos suppositions, ce mot est dans L
	    -- comme c1+2c2+c3 = (c1+c2+c3) +c2 avec c2>0, le nombre
	    de a est strictement suppérieur au nombre de b, donc ce
	    mot n'est pas dans L.

Il y a une contradiction, donc L n'est pas régulier.

---------------------------------------------------------------------

L2={mots sur {a,b}, meme nombre de a que de b}

Supposons L2 régulier, alors L2 inter {a^nb^m|m,n>=0} = L1. Or
{a^nb^m|m,n>=0} est régulier, donc L1 est régulier (les langages
réguliers sont stables par intersection.) On a montré que L1 n'est pas
régulier, contradiction. L2 n'est donc pas régulier.

----------------------------------------------------------------------

L3= 0^i.1^j.2^(i+j)

Même schéma de preuve avec le lemme de l'étoile en prenant
w=0^N.1^N.2^(2N)

------------------------------------------------------------------------

L4 = {0^i, i premier}

Supposons L4 régulier, et soit N la constante fournie par le lemme de
l'étoile pour L4.
pour exhiber un w qui va fournir le CE pour le lemme de l'étoile, il
faut que w appartienne à l'étoile, il faut donc que w=0^N0, avec N0
premier plus grand que N. Prenons par exemple le premier N0 plus grand
ou égal à N ( il existe car les nombres premiers sont en nombre
infini).

Alors w=0^N0 se décompose en xyz, x=0^a, y=0^b z=0^c avec a+b<=N,
a+b+c=N0 et >0.

Alors les xy^kz sont de la forme  0^(a+kb+c), et il faut donc trouver
une valeur judicieuse de k pour que a+kb+c se factorise ..
Prenons donc k=a+c, alors xy^kz= 0^((a+c)(b+1)) et donc l'exposant se
factorise, il reste donc à montrer que les deux facteurs sont >1 :
	   -- b+1>1 car b>0 
	   -- a+c ??? on a d'après les contraintes induites par la
	   décomposition c>=N0-N arg, on ne peut pas à ce stade
	   prouver que c>1. Mais au début, on pouvait très bien
	   choisir un N0 plus gros.
donc, il suffit de choisir N0 un nombre premier >=N+2 et le tour est
joué.
On a donc trouvé un k tel que xy^kz n'est pas dans L, donc L n'est pas
régulier.

---------------------------------------------------------------------------

L5 = { mots sur {0,1}, taille premier}

L5 inter {0^n|n>=0}=L4 qui n'est pas premier.

---------------------------------------------------------------------------

L6 = { 0^i | il existe n, i=n^2} autre demo que le cours.

Supposons L6 rationnel . soit N0 la constante donnée par le lemme de
l'étoile. Prenons w un mot de L6 de taille >=N0. alors w s'écrit xyz
avec tous les xy^kz dans L6. Les tailles des mots xy^kz forment une
suite arithmétique : alpha + beta n où alpha=|x|+|z| et beta = |y|,
beta>0. 
or les tailles des mots de L6 sont 4 9 25 36, et entre 2 tailles
consécutives (n+1)^2-n^2 = 2n+1, qui tend vers +infini.
Or les mots de taille alpha+beta n sont espacés de beta constant.
donc, au bout d'un certain temps, 2n+1 >beta et donc la suite des mots
de L6 ne peut contenir une suite de mots dont la taille est une suite
géométrique. contradiction avec le fait que tous les éléments de cette
suite doivent appartenir à L6.


---------------------------------------------------------------------------