Chapitre 3
Solution de l'exercice 6.1

Montrer que les langages suivants ne sont pas rationnels :

1. {aⁿb^p : n < p} , A={a,b}
• Démonstration par le lemme de l'étoile : Prenons un entier N suffisamment grand. Pour tout mot z du langage tel que |z|≥N, il existe u, v, w de A* tels que z=uvw, |v|>0, |uv|≤N alors, normalement, pour tout entier i le mot uvⁱw est dans {aⁿb^p : n < p} (?)
• Le mot qui fait mal ! Prenons le mot z=a^Nb^N+k avec k≥1
• Si z=uvw alors u=a^p, v=a^q avec q>0 et w=a^N-(p+q)b^N+k
• Donc z = a^p a^q a^N-(p+q)b^N+k
• uvⁱw = a^p (a^q)ⁱ a^N-(p+q)b^N+k = a^N (a^q)^i-1 b^N+k = a^N+q(i-1) b^N+k
• Or pour tout i > 1+k/q uvⁱw n'est plus dans {aⁿb^p : n < p} car alors N+(i-1)q > N+k ! Donc il ne vérifie pas le lemme de l'étoile et donc il n'est pas rationnel ! CQFD
2. {(aⁿ)ⁿ} = {a^p : p = n²} = {a^{n^2}}, c'est-à-dire les mots composés de "a" et dont la longueur est un carré.
• Démonstration par le lemme de l'étoile : Prenons un entier N suffisamment grand. Pour tout mot z du langage tel que |z|≥N, il existe u, v, w de A* tels que z=uvw, |v|>0, |uv|≤N alors, normalement, pour tout entier i le mot uvⁱw est dans {a^{n^2}} (?)
• Soit N=m², Prenons le mot z=a^{(m+1)^2} = a^2maa^{m^2} (car (a+b)² = a²+2ab+b²)
• Si z=uvw alors u=a^2m, v=a et w=a^{m^2}
• |uv| < N si m >= 1+racine(2),
• Donc z = a^2maa^{m^2}
• uvⁱw = a^2maⁱa^{m^2}
• Or pour i = 2 uvⁱw n'est plus dans {a^{n^2}} car alors 2m+2+m² n'est pas un carré ! En effet, le prochain carré après (m+1)² est (m+2)²=m²+4m+4. Or m²+2m+1 < 2m+m+m² < m²+4m+4
• Donc il ne vérifie pas le lemme de l'étoile et donc il n'est pas rationnel ! CQFD
3. L = {aⁿb^p : n ≠ p}
   • Procédons par l'absurde en supposant que ce langage est rationnel.
   • Donc son complémentaire Comp(L) est rationnel.
   • Attention, ce complémentaire contient toute sorte de mots tel que "bbababa" !
   • Si Comp(L) est rationnel, alors Comp(L) ∩ a*b* est rationnel (intersection de deux langages rationnel est rationnel).
   • Or Comp(L) ∩ a*b* = {aⁿbⁿ : n≥0} qui n'est pas rationnel !
   • Il y a donc contradiction ! donc il n'est pas rationnel ! CQFD

mardi, 9/12/03 16:08