Les langages rationnels sont exactement les langages reconnaissables par les automates finis (qui sont présentés plus loin) et donc, pour montrer qu'un langage est rationnel, la méthode la plus courante consiste à produire soit une expression rationnelle standard qui lui correspond, soit un automate fini qui le reconnaît.
De manière générale, par contre, il n'est pas toujours facile de montrer qu'un langage n'est pas rationnel. Pour cela, on utilise souvent le théorème suivant :
Intuitivement : pour tout langage rationnel L, il existe une taille de mot n à partir de laquelle tout mot de L plus long possède au moins un facteur itérant dans ses n premières lettres.
Remarque : il existe bien d'autres formulations de ce lemme avec des propriétés parfois un peu différentes. Un début de discussion à ce propos se trouve dans [Séébold 99]. Il présente un lemme de l'étoile "fort" et un lemme de l'étoile "faible". Celui présenté dans ce cours est le second.
En fait, ce lemme peut s'appliquer à des langages qui ne sont pas rationnels mais tout langage rationnel vérifie ce lemme. Autrement dit, Rat(A*) ⊂ Etoile(A*) ⊂ P(A*)
Ce théorème
permet souvent de démontrer par l'absurde qu'un langage
L n'est pas rationnel : il suffit de montrer que, pour tout
n de N, il existe un mot z de L qui ne vérifie
pas la condition pour un i donné. Mais attention, un
mot peut ne pas fonctionner parce que trop court ! Généralement,
il n'est pas nécessaire de trouver le n. C'est vrai pour tout n'>n,
il n'est donc pas nécessaire de trouver le n optimal. En effet, si le
facteur itérant est dans le n premières lettres alors il est aussi
dans les n' premières.
Par contre,
montrer qu'un langage vérifie le lemme de l'étoile ne
prouve pas qu'il est rationnel. Si le lemme de l'étoile ne permet
pas de prouver qu'un langage est rationnel, une piste possible est de faire
une démonstration par l'absurde en cherchant à démontrer
qu'il est rationnel.
Un exemple, si l'on reprend l'exemple de {ambm | m ∈ N} (un grand classique !), la démonstration prend la forme suivante :
| Hypothèses : | Il existe un entier positif n ∈ N, tel que ∀ z ∈ L, |z| > n, (H1)∃ u,v,w, tels que z=uvw, (H2) v ≠ ε, (H3) |uv| ≤ n, (H4) ∀i ∈ N, uviw ∈ {ambm | m ∈ N} |
| Le mot qui va poser problème : | Considérons le mot z=anbn (|z|=2n, donc |z|>n). Soient u,v et w tels z=uvw (H1) et vérifiant H2, H3 et H4 (z est plus long que n et par hypothèse, u,v et w existent). |
| La contradiction : | Tout préfixe de z de longueur l ≤ n est nécessairement composé uniquement de a. Comme uv est un préfixe de z (H1 : z=uvw) et |uv|<n (H3), ceci est vrai en particulier de uv. Donc il existe k,p ∈ N (p ≠ 0) tels que u=ak, v=ap (H2 : v ≠ ε) et k+p ≤ n. Et on a z=uvw=akapw, avec w=an-(k+p)bn (car z=anbn). H4 s'écrit alors or ceci est faux : et, comme p ≠ 0, pour n'importe
quel i > 1, |
| Conclusion : | Donc l'hypothèse est fausse. Donc, par le théorème de l'étoile, {ambm | m ∈ N} n'est pas un langage rationnel. |
Remarquons à nouveau que ce lemme ne peut pas servir à démontrer qu'un langage est rationnel : il existe en effet des langages non rationnels qui le vérifient (par exemple L = {ambpcp | m,p ∈ N et m > p} : il suffit de considérer n=2, car tout mot de L plus long que 2 commence nécessairement par 2 a et l'on peut itérer à volonté le deuxième a, par exemple, sans sortir du langage L).
Notons aussi que, assez souvent, lorsqu'il y a "relation" entre les éléments de l'expression, le langage n'est pas rationnel. Mais attention, ceci est un indice et non une règle universelle.
Exercices et tests :
Exercice 6.1. Montrer que
les langages suivants ne sont pas rationnels 
:
Exercice 6.2. Les langages suivants sont-ils rationnels ? Le prouver.
mardi, 25/11/03 10:27
