Exercices automates et cloture des langages reconnaissa...

Théorie des langages : Exercices automates et cloture des langages reconnaissables

Télécharger PDF

Feuille 2 - Constructions d’automates et clôture des langages reconnaissables

Informatique Théorique 2 - Unité J1INPW11

Licence 3 - Université Bordeaux 1

Exercice 1 : Quelques exemples d’automates

Dessiner, si possible, un automate fini et une expression régulière pour les langages suivants construits sur l’alphabet {a, b} :

1. Tous les mots qui contiennent le facteur bab

Un automate fini peut reconnaître ce langage en utilisant un état intermédiaire pour détecter la séquence bab. L’expression régulière correspondante est : a*bab*a*.

2. Tous les mots qui ne contiennent pas le facteur bab

Un automate fini peut être construit en évitant l’état qui reconnaît bab. L’expression régulière est : (a + b)* - bab.

3. Tous les mots qui ne contiennent pas de facteur aba suivi de 2ⁿb où n est un entier quelconque

Ce langage est plus complexe et nécessite une analyse des répétitions de a et b. Un automate fini peut être conçu pour rejeter les mots contenant cette structure.

4. Tous les mots qui contiennent un nombre pair de a et un nombre impair de b

Un automate fini avec comptage modulo 2 pour a et b peut être utilisé. L’expression régulière est : (a² + a²b + ba² + b)(a²b + ba² + b2b + ba² + b)*).

5. L’ensemble des mots contenant un nombre de a congru à 2 modulo 5

Un automate fini avec 5 états pour compter les occurrences de a modulo 5 peut reconnaître ce langage. L’expression régulière est plus complexe et nécessite une construction basée sur les puissances de a.

6. L’ensemble des mots de longueur au moins n où n est un entier naturel fixé

Un automate fini avec un état initial non final et n transitions successives vers un état final peut reconnaître ce langage. L’expression régulière est : (a + b)ⁿ(a + b)*.

7. L’ensemble des mots contenant autant de a que de b

Un automate fini avec un comptage équilibré de a et b peut être utilisé. L’expression régulière est : (aⁱbⁱ + bⁱaⁱ)(a + b)*.

Démontrer que les automates donnés reconnaissent bien ces langages et que les expressions régulières les décrivent.

Exercice 2 : Division par 3

Construire un automate déterministe fini qui reconnaît l’ensemble des représentations binaires des entiers positifs divisibles par 3. Deux versions sont demandées :

1. Lecture de gauche à droite

Un automate fini avec 3 états (représentant les restes 0, 1, 2) peut être utilisé pour valider cette propriété.

2. Lecture de droite à gauche

Un automate fini inversé, utilisant des transitions basées sur les puissances de 2, peut reconnaître les mots binaires divisibles par 3.

Exercice 3 : Union, intersection, complémentaire, concaténation et étoile

1. Ensembles de mots L₁ et L₂

Soit L₁ = {aa, baa, ab, aba} et L₂ = {bbb, a, ab} deux ensembles de mots. Donner les mots contenus dans les ensembles suivants :

L₁ ∪ L₂ : {aa, baa, ab, aba, bbb, a}
L₁ ∩ L₂ : {ab}
L₁ • L₂ (concaténation) : {aabbb, aaba, aab, baabbb, baaba, baab, abbbb, abbb, abaabbb, abaaba, abaab, abab}
L₁ \ L₂ : {aa, baa, aba}
(L₂)² : {bbb bbb, bbb a, bbb ab, a bbb, a a, a ab, ab bbb, ab a, ab ab}
(L₂)* : tous les mots formés par répétition de {bbb, a, ab}, y compris la chaîne vide
(a + b)* \ L₁ : tous les mots de {a, b}* qui ne sont pas dans L₁

2. Suppression des ε-transitions

Pour l’automate suivant (représenté en notation textuelle), supprimer les transitions ε :

État 1 : transitions vers 2, 3, 4, 5, 6, 7, 8
État 2 : transition vers 3 avec a
État 3 : transition vers 4 avec b
État 4 : transition vers 5 avec b
État 5 : transition vers 6 avec a
État 6 : transition vers 7 avec a
État 7 : transition vers 8 avec b
État 8 : transition vers 1 avec a
État 1 : transition ε vers 1

3. Automates A₁ et A₂ avec opérations sur les langages

Construire des automates qui reconnaissent les langages suivants pour les automates A₁ et A₂ donnés :

L(A₁) ∪ L(A₂) : union des langages
L(A₁) ∩ L(A₂) : intersection des langages
L(A₁) • L(A₂) : concaténation des langages
(L(A₂))² : répétition de L(A₂)
(L(A₂))* : fermeture de Kleene de L(A₂)
L(A₁) \ L(A₂) : différence entre L(A₁) et L(A₂)
(a + b)* \ L(A₂) : complémentaire de L(A₂)

Proposer des constructions avec et sans ε-transitions.

Exercice 4 : Démonstration de quelques propriétés de clôture sur les langages reconnaissables

1. Suppression des ε-transitions d’un automate

Pour supprimer les ε-transitions, transformer l’automate en un automate sans ε en remplaçant chaque ε-transition par une transition directe vers les états accessibles par ε.

2. Clôture des langages reconnaissables par union, intersection, concaténation, étoile et complémentaire

Montrer que pour tout automate fini A₁ et A₂ reconnaissant les langages L₁ et L₂, les opérations suivantes préservent la reconnaissabilité :

Union : L₁ ∪ L₂
Intersection : L₁ ∩ L₂
Concaténation : L₁ • L₂
Étoile : L₁*
Complémentaire : (a + b)* \ L₁

FAQ

Qu’est-ce qu’un automate fini déterministe (AFD) ?

Un automate fini déterministe est un modèle mathématique utilisé en informatique théorique pour reconnaître les langages formels. Il se compose d’un ensemble fini d’états, d’un alphabet, d’une fonction de transition déterministe, d’un état initial et d’un ensemble d’états finaux.

Comment construire un automate pour reconnaître un langage avec un nombre pair de a ?

Utiliser un automate avec deux états : un état initial (non final) et un état final. Ajouter une transition sur a entre l’état initial et final, puis une autre transition sur a de l’état final vers l’état initial. Cela assure que le nombre de a est pair.

Quelle est la différence entre une ε-transition et une transition normale ?

Une ε-transition permet de passer d’un état à un autre sans consommer de symbole de l’alphabet, contrairement aux transitions normales qui consomment un symbole spécifique. Les ε-transitions sont souvent utilisées pour modéliser des choix ou des actions internes dans un automate.