Théorie des langages : Exercices automates et cloture des langages reconnaissables
Télécharger PDFFeuille 2 - Constructions d’automates et clôture des languages
reconnaissables
Informatique Théorique 2 - Unité J1INPW11
Licence 3 - Université Bordeaux 1
Exercice 1Quelques 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 facteurbab;
2. tous les mots qui ne contiennent pas le facteurbab;
3. tous les mots qui ne contiennent pas de facteuraba2n baoùnest un entier quelconque ;
4. tous les mots qui contiennent un nombre pair deaet un nombre impair deb.
5. l’ensemble des mots contenant un nombre deacongru à2modulo5;
6. l’ensemble des mots de longueur au moinsnoùnest un entier naturel fixé.
7. l’ensemble des mots contenant autant deaque deb.
Démontrer que les automates donnés reconnaissent bien ces langages et les expressions régu-
lières les décrivent.
Exercice 2Division par 3
Construisez un automate déterministe fini qui reconnait l’ensemble des représentations
binaires des entiers positifs divisibles par 3. Vous proposerez deux versions de cet automate.
La première reconnaitra ces mots en lisant les mots de la gauche vers la droite. La deuxième
les reconnaitra en lisant de la droite vers la gauche.
Exercice 3Union, intersection, complémentaire, concatenation et étoile
1. SoitL1 ={aa, baa, ab, aba}etL2 ={bbb, a, ab}deux ensembles de mots. Donner les
mots contenus dans les ensembles suivants :L1 ∪L2 ,L1 ∩L2 ,L1 •L2 ,L1 \L2 ,(L2 )2 ,(L 2) ∗et(a+b) ∗\L 1
, où•est l’opération de concaténation.
2. Enlevez lesǫ-transitions de l’automate suivant :1 12345 678aa bba aa bb bba ba ǫ
Figure1 – AutomateA
3. Soit les automatesA1 etA2 des figures 2 et 3.1 23 abb a
Figure2 – AutomateA1 12 3a ba ab Figure3 – AutomateA2 Construisez des automates qui reconnaissentL(A1 )∪L(A2 ),L(A1 )∩L(A2 ),L(A1 )•L(A 2),(L(A 2)) 2,(L(A 2)) ∗,L(A 1)\L(A 2
), et(a+b)∗ \L(A2 )où•est la concatenation
des mots. Vous proposerez des constructions avec et sansǫ-transitions.
Exercice 4Démonstration de quelques propriétés de clôture sur les languages reconnais-sables 1. Montrer que l’on peut supprimer lesǫ-transitions d’un automate ;
2. Montrer que la classe des languages reconnaissables est close par union, intersection,
concaténation, étoile et complémentaire.
2