UNIVERSITE MUSTAPHA STAMBOULI MASCARA
Faculté de Sciences Exactes Département D’informatique
Module : Compilation /TD01 2024-2025
Exercice 1 :
Soit la grammaire G, tel que G=<{a,b,c}, {S,A,B,C}, S, P> ,
P= S→aA , S→bS , A→aB , A→cC , B→bS , B→ε , C→bA , C→ε
Convertir cette grammaire en un automate d’état fini.
Exercice2 :
Soit l’automate suivant : États : Q={q0,q1,q2} Alphabet : Σ={x,y} État initial : q0 - États finaux : q2
Transitions : - δ(q0,x)=q1 - δ(q0,y)=q2 - δ(q1,x)=q1 - δ(q1,y)=q2
Transformez cet automate en grammaire régulière droite.
Exercice3 :
Sur l’alphabète {a,b} donner une grammaire qui accepte les mots qui commencent par un b et avec un
nombre pair de 'a'.
Exercice4 :
Sur l’alphabète {a,b} donner un automate d’état fini pour les langages suivants :
- Le langage des mots contenant au plus une fois la lettre a,
- Le langage des mots contenant au moins une fois la lettre a,
- Les mots qui commencent et se terminent par la même lettre.
Exercice5 :
Considérons l'alphabet Σ={0,1},
1. Définir une grammaire régulière qui génère tous les mots qui commencent par '0' et se terminent par '1'.
2. Transformez cette grammaire régulière en un automate fini.
3. Donnez quelques exemples de mots générés par cette grammaire et montrez leur acceptation par
l'automate fini.
Exercice 6 :
Soit l’AFN A suivant :
Indiquer tous les chemins étiquetés
par aabb
A accepte-t-il b,ab,ba, abaabb ?
Donner sa table de transition
Déterminiser A
Exercice 7 :
Construisez un automate fini non déterministe à partir de l'expression régulière suivante: L=ab*(ab)ba*
Donner l'automate déterministe correspondant.
Exercice 8
b
a
Considérez l'automate suivant : 0 1
1. Vérifiez si cet automate est déterministe.
b a b
2. Si ce n'est pas le cas, déterminez-le.
3. Minimisez l'automate obtenu. a b
2 3
