Théorie des langages : Td 4 automates de programmation
Télécharger PDFUniversité de Technologie de Compiègne - Théorie des Langages de Programmation
TD 4 : Automates - Corrigé
Dans ce TD, nous étudions les automates finis déterministes (AFD), les automates non déterministes (AFN) et les automates avec epsilon-transitions (eps-AFD).
Exercice 1
Construire les automates d’états finis simples et déterministes acceptant les langages dénotés par les expressions régulières suivantes :
-
L’expression régulière E1 = ab(a|b)* décrit un langage où la chaîne commence par "ab" suivie de zéro ou plusieurs "a" ou "b".
Exemple : "ab", "abb", "abaa", etc.
-
L’expression régulière E2 = 110*1 décrit un langage où la chaîne commence par "11", suivie de zéro ou plusieurs "0", puis se termine par "1".
Exemple : "111", "1101", "110001", etc.
-
L’expression régulière E3 = aa* | b décrit un langage où la chaîne commence par "a", suivie de zéro ou plusieurs "a", ou est simplement "b".
Remarque : La concaténation a une priorité plus élevée que la disjonction. Ainsi, E3 est différent de E′3 = a(a* | b), où la disjonction est prioritaire.
Construire des automates (AFD, AFN ou eps-AFN) pour les expressions régulières suivantes :
-
L’expression régulière E4 = (a|b)*ab(a|b)* décrit un langage où la chaîne contient "ab" quelque part, entourée de zéro ou plusieurs "a" ou "b".
Exemple : "ab", "aabb", "bba", "aabab", etc.
-
L’expression régulière E5 = (ab)* (baa)* aa décrit un langage où la chaîne est composée de répétitions de "ab" et "baa", suivie de "aa".
Exemple : "aa", "abbaa", "ababbaa", "baabaa", etc.
Remarque : Les automates non déterministes avec epsilon-transitions peuvent simplifier la construction.
Exercice 2
Construire des automates finis déterministes pour les langages suivants :
-
L’ensemble des constantes composées de cinq chiffres maximum, avec ou sans zéros à gauche.
Exemple : "123", "00045", "0", "12345", etc.
-
L’ensemble des chaînes composées de lettres, chiffres et tirets, sans tiret en début ou fin, et sans deux tirets consécutifs.
Exemple : "abc-123", "A1B2", "lettres-123", etc.
L’automate peut accepter ou refuser la chaîne vide selon les besoins.
-
L’ensemble des chaînes de 0 et 1 où chaque 0 est immédiatement suivi d’au moins un 1.
Exemple : "1", "01", "101", "0110", etc.
L’automate peut accepter ou refuser la chaîne vide selon les besoins.
-
L’ensemble des chaînes formées de lettres où les consonnes sont séparées par des voyelles (pas de consonnes consécutives).
Exemple : "a", "ae", "aie", "eau", "oie", etc.
L’automate peut accepter ou refuser la chaîne vide selon les besoins.
Exercice 3
Soit l’automate A donné par sa table de transition :
| État | a | b | c |
|---|---|---|---|
| S0 | S3 | S2 | S2 |
| S1 | S2 | S1 | S2 |
| S2 | S2 | S2 | ∗ |
| S3 | S1 | S3 | S1 |
1. Trouver l’automate déterministe équivalent C tel que L(A) = L(C).
2. Convertir l’automate non déterministe A en un automate déterministe C en utilisant l’algorithme de conversion.
Exemple de table de transition intermédiaire (avant renumérotation) :
| État | a | b | c |
|---|---|---|---|
| q0 | q3 | q2 | q2 |
| q1 | q2 | q1 | q2 |
| q2 | q2 | q2 | ∗ |
| q3 | q1 | q3 | q1 |
Exercice 4
Soit l’automate A donné par sa table de transition avec epsilon-transitions :
| État | a | b | c | ε |
|---|---|---|---|---|
| S0 | fer(S0) | S0 | ||
| S1 | fer(S1) | fer(S2) | fer(S1) | S1, S2 |
| S2 | fer(S2) | fer(S2) | ∗ | S2 |
| S3 | fer(S3) | fer(S1) | S3 |
1. Trouver un automate déterministe équivalent C tel que L(A) = L(C).
2. Trouver un automate déterministe B tel que L(B) = Miroir(L(A)).
FAQ
1. Qu’est-ce qu’un automate fini déterministe (AFD) ?
Un AFD est un modèle mathématique qui reconnaît un langage formel en utilisant un ensemble fini d’états et une fonction de transition unique pour chaque état et symbole d’entrée.
2. Comment construire un automate équivalent sans epsilon-transitions ?
Utilisez l’algorithme ε-fermeture pour supprimer les transitions epsilon, puis appliquez la construction des états équivalents pour obtenir un AFD.
3. Pourquoi la chaîne vide est-elle parfois acceptée ou refusée dans les automates ?
Cela dépend de la définition du langage. Certains automates doivent explicitement accepter ou refuser la chaîne vide pour correspondre à la spécification donnée.