TD Automates, langages et applications

Ce document présente un corrigé de TD en Automates, langages et applications, visant à tester la compréhension des langages réguliers, l'application du lemme de pompage, la construction d'automates, ainsi que la reconnaissance des propriétés des langages comme les palindromes.

Exercice 1 : Lemme de pompage

On demande de déterminer si les langages suivants sont réguliers :

• L1 = {0^(2n) | n ≥ 1}
• L2 = {0^(2n) | n ≥ 1} (même que L1, mais traité différemment)
• L3 = {0^n 1^n | n ≥ 1}
• L4(n) = {x ∈ {0,1}* | n0(x) ≡ n1(x) mod n}, où n0(x) et n1(x) sont le nombre de 0 et de 1 dans x
• L5 = {x ∈ {0,1}* | x ne contient pas 3 zéros consécutifs}
• L6 = {0^n | n premier}

Analyse et solutions

1. Langage L1

L1 = {0^(2n) | n ≥ 1} peut s'écrire comme 00(00)*, c’est-à-dire une chaîne commençant par deux zéros suivis de zéro ou plusieurs occurrences de "00".

Cette expression régulière montre que L1 est un langage régulier.

Réponse : L1 est régulier.

2. Langage L2

Supposons que L2 soit régulier. Prenons n ≥ 1 donné par le lemme de pompage. Considérons le mot z = 0^(2n) ∈ L2.

Selon le lemme de pompage, on peut écrire z = uvw avec |v| ≤ n et uv^2w ∈ L2.

Or, la longueur de uv^2w est |u| + 2|v| + |w| = 2n + |v| ≤ 2n + n = 3n.

Mais 3n n'est pas nécessairement un multiple de 2, donc uv^2w ne peut pas être dans L2 (qui ne contient que des puissances de 0 de longueur multiple de 2).

Cette contradiction montre que L2 n'est pas régulier.

Réponse : L2 n'est pas régulier.

3. Langage L3

L3 = {0^n 1^n | n ≥ 1} est un langage classique non régulier. Pour le montrer, on applique le lemme de pompage.

Soit n ≥ 1, prenons z = 0^n 1^n ∈ L3. On écrit z = uvw avec |uv| ≤ n et |v| ≥ 1.

Le segment v est donc composé uniquement de 0 (car les n premiers caractères sont des 0).

En pompant v (c’est-à-dire en prenant uv^2w), on ajoute des 0 sans ajouter de 1, ce qui donne une chaîne de la forme 0^(n+|v|) 1^n.

Cette chaîne n’appartient pas à L3 car le nombre de 0 et de 1 n’est plus égal.

Contradiction, donc L3 n’est pas régulier.

Réponse : L3 n’est pas régulier.

4. Langage L4(n)

L4(n) = {x ∈ {0,1}* | n0(x) ≡ n1(x) mod n} est reconnu par un automate où chaque état représente la différence n0(x) - n1(x) modulo n.

Un tel automate peut être construit avec n états, chacun correspondant à un résidu modulo n.

Les transitions mettent à jour cette différence en fonction du symbole lu (0 ou 1).

Par conséquent, L4(n) est régulier.

Réponse : L4(n) est régulier.

5. Langage L5

L5 = {x ∈ {0,1}* | x ne contient pas 3 zéros consécutifs} est régulier car il est reconnu par un automate qui compte jusqu’à deux zéros consécutifs et rejette si un troisième zéro suit.

Un automate fini avec un nombre fini d’états (par exemple 4 états : aucun zéro récent, un zéro récent, deux zéros récents, état de rejet) suffit à reconnaître ce langage.

Réponse : L5 est régulier.

6. Langage L6

L6 = {0^n | n premier} est supposé régulier pour contradiction.

Soit n ≥ 1 donné par le lemme de pompage. Choisissons p > n un nombre premier et z = 0^p ∈ L6.

On écrit z = uvw avec |v| ≥ 1 et |uv| ≤ n.

En pompant v, on obtient uv^(p+1)w de longueur |u| + (p+1)|v| + |w| = p + |v|p = p(1 + |v|), qui est un multiple de p.

Cette longueur n’est donc pas un nombre premier (sauf si |v|=0, ce qui est impossible), donc uv^(p+1)w ∉ L6.

Contradiction, donc L6 n’est pas régulier.

Réponse : L6 n’est pas régulier.

Exercice 2 : Inverse d’une chaîne et palindromes

1. Construction d’un automate reconnaissant le langage inverse LR

On demande de décrire une méthode pour construire, à partir d’un automate M reconnaissant L, un automate M' reconnaissant LR, le langage des inverses des mots de L.

La méthode est la suivante :

• Inverser toutes les transitions de M (changer la direction des arcs).
• Transformer les états finaux de M en états de départ de M'.
• Créer un nouvel état initial unique dans M' avec des transitions epsilon (ε) vers tous les anciens états finaux de M.
• Faire de l’ancien état initial de M l’unique état final de M'.

Cette construction garantit que M' reconnaît exactement les inverses des mots reconnus par M.

Réponse : Construire M' en inversant les transitions de M, en ajoutant un nouvel état initial avec des transitions ε vers les anciens états finaux, et en faisant de l’ancien état initial de M l’état final unique de M'.

2. Non-régularité du langage des palindromes

Les palindromes sont les mots qui se lisent de la même manière à l’endroit et à l’envers, c’est-à-dire w = wR.

On doit montrer que le langage des palindromes n’est pas régulier.

Supposons que le langage des palindromes L soit régulier sur l’alphabet {0,1}.

Soit n ≥ 1 donné par le lemme de pompage. Considérons le mot palindrome z = 0^n 1 0^n ∈ L.

On écrit z = uvw avec |uv| ≤ n et |v| ≥ 1.

Comme |uv| ≤ n, u et v sont composés uniquement de 0.

En pompant v, on obtient z' = uv^2w = 0^{n + |v|} 1 0^n.

Or z' n’est pas un palindrome car le nombre de 0 avant et après le 1 n’est plus égal.

Contradiction avec le lemme de pompage, donc le langage des palindromes n’est pas régulier.

Réponse : Le langage des palindromes n’est pas régulier.

Méthode

Ce TD récompense la maîtrise du lemme de pompage pour démontrer la non-régularité des langages, ainsi que la capacité à construire des automates et à raisonner sur leurs propriétés.

Les erreurs fréquentes à éviter sont :

• Ne pas appliquer correctement le lemme de pompage, notamment en choisissant un mot adapté.
• Oublier que les pompages doivent rester dans le langage pour valider la régularité.
• Confondre les états initiaux et finaux lors de la construction de l’automate inverse.
• Ne pas justifier clairement les contradictions obtenues.

Il est important de toujours expliciter les étapes intermédiaires et de vérifier la cohérence des longueurs et des propriétés des mots manipulés.