Théorie des langages : Exercices automates finis et expressions rationnelles
Télécharger PDFFeuille 1 - Automates finis et expressions rationnelles
Informatique Théorique 2 - Unité J1INPW11
Licence 3 - Université Bordeaux 1
Exercice 1Langage associé à une expression régulière
Donner tous les mots de tailles 0, 1, 2, 3, et 4 des langages réguliers suivants :
1.(a+ba)∗ 2.a(aa+b(ab)∗ a)∗ a
Exercice 2Expression régulière d’un langage
Sur l’alphabet{a, b}, donner une expression régulière pour
1. le langage des mots qui entre deux occurrences de la lettreaont un nombre pair deb.
2. le langage des mots tels que toutes les (éventuelles) occurrences deaprécèdent toutes
les (éventuelles) occurrences deb.
Exercice 3Langage reconnu par un automate
Donner tous les mots de longueurs 0, 1, 2, 3 et 4 reconnus par les automates de la figure
1 et 2.123 4ab ab ba a
Figure1 – AutomateA1 12 34b ba ba a
Figure2 – AutomateA2
Exercice 4De l’automate à la définition mathématique
Pour les automates de la figure 1 et 2, donnez leurs définitionsmathématiques.
Exercice 5De la définition mathématique à l’automate
Pour chacune des deux définitions mathématiques suivantes,dessiner l’automate qui le
représente.A 3= Q={1,2,3}, qi = 1, F={2,3}, δ: (1, a)→2
(1, b)→2
(2, c)→2
(2, a)→3
(3, b)→1 1 A4 =
Q={1,2,3}, qi = 2, F={2}, δ: (1, a)→1
(1, b)→2
(3, a)→3
(2, b)→1
Exercice 6Quelques exemples d’automates
Donner, si possible, un automate et une expression régulière pour les langages suivants
construits sur l’alphabet{a, b, c}:
1. tous les mots ;
2. tous les mots sansb;
3. tous les mots contenant au plus une occurrence de la lettrea;
4. tous les mots contenant au moins une occurrence de la lettrea;
5. tous les mots dans lesquels chaqueaest suivi d’unb;
6. pour un mot donnéx,{x};
7. tous les mots de longueur paire ;
8. tous les mots avec le prefixeab;
9. tous les mots avec le suffixeab;
Démontrer que les automates donnés reconnaissent bien ces langages et les expressions régu-
lières les décrivent.
Exercice 7Exercice plus difficile et recommandé en travail personnel
Étant donné un alphabetAet un motxdeA∗ , construire un automate déterministe à|x|
états qui reconnaîtA∗ x.
Exercice 8Quelques identités sur les langages
SoientKetLdeux langages etL+ =[ i>0L i. Est-ce que les identités suivantes sont-elles correctes ?1.L +=LL ∗2.LL ∗=L ∗
\ {ǫ}3.L ∗=ǫ+LL ∗4.(KL) ∗K=K(LK) ∗
Justifier vos réponses.
Exercice 9Expression régulière d’un automate
Donnez sous forme d’expressions régulières les langages reconnus par les automates de
la figure 1 et 2. Vous calculerez ces expressions régulières avec deux méthodes différentes
(algorithme de résolution des équations, l’algorithme McNaughton et Yamada,. . .).
Exercice 10Automate d’une expression régulière
A l’aide de l’algorithme de Glushkov, donnez des automates finis (sans transitionsǫ) qui
reconnaissent les langages suivants :
1.aa(a+ab)∗ b2 2.(a+ab)∗ (ǫ+ab)3.aab ∗(ab) ∗+ab ∗+a ∗bba 4.a((ab)∗ cb∗ )∗ +a(ababacb∗ )∗ a∗
Exercice 11Automate deterministe ou non déterministe ?
Les automates suivant sont-ils déterministe ou non déterministe ? Pourquoi ?12 4a ba a
Figure3 – AutomateA5 124 aa bb aa Figure4 – AutomateA6 Donner des exemples d’automate déterministe et non déterministe.
Exercice 12Déterminisation d’un automate
1. Proposer un automate non deterministe qui reconnait les mots qui se terminent parab.
Determiniser cet automate.
2. Déterminiser les automates de l’exercice 11.
3