Théorie des langages : Td 4 automates de programmation
Télécharger PDFUniversité de Technologie de Compiègne
NF11 - Théorie des Langages de Programmation
TD 4 Automates : Corrigé
Dans ce TD nous abordons les automates finis déterministes (AFD), les automates
non déterministes (AFN) et les automates avec epsilon-transition (eps-AFD).
Exercice 1Construire les automates d’états finis simples et déterministes acceptant
les langages dénotés par les expressions régulières suivantes :
1. Soit l’expression régulièreE1 =ab(a|b)∗ :
Figure1 – Automate reconnaissantL(E1 )
2. Soit l’expression régulièreE2 = 110∗ 1:
Figure2 – Automate reconnaissantL(E2 )
3. Soit l’expression régulièreE3 =aa∗ |b. L’automate reconnaissant le langage
engendré par l’expression régulièreE3 est donné par la Figure 3. On rappelle
Figure3 – Automate reconnaissantL(E3 )
que l’opérateur concaténation est plus prioritaire que l’opérateur de disjonc-
tion. Il ne faut confondre l’expression régulièreE3 avec l’expression régulière
suivante :E′ 3=a(a ∗
|b)où on force la priorité de l’opérateur de disjonction
grâce aux méta symboles parenthèses.
On donne aussi, dans la Figure 4, l’automate reconnaissant le langageL(E′ 3) (non demandé dans l’exercice).
Construire des AFD, AFN ou eps-AFN acceptant les langages dénotés par
les expressions régulières suivantes.
1. Soit l’expression régulièreE4 = (a|b)∗ ab(a|b)∗ . On remarque que l’automate de
la Figure 5 est non déterministe.1 Figure4 – Automate reconnaissantL(E3 )
Figure5 – Automate reconnaissantL(E4 )
2. Soit l’expression régulièreE5 = (ab)∗ (baa)∗ aa. On remarque que l’automate,
de la Figure 6, contient destransition.
Remarque :Il est généralement plus naturel et plus facile de construire des auto-
mates non déterministes avec-transition. On rappelle qu’il existe une équivalence
entre AFD, AFN et eps-AFN. A titre d’exemple on donne un AFD (Figure 7) qui
reconnait le langageL(E5).
D’une manière générale on peut utiliser l’algorithme vu en cours pour obtenir un
automate fini déterministe.
Exercice 2Construire les automates d’états finis simples et déterministes acceptant les langages
suivants :
1. L’ensemble des constantes composées de cinq chiffres maximum.
SoitC= [0−9]etC0 = [1−9].
— La Figure 8 représente une solution possible où on autorise la présence d’un
ou plusieurs zéros à gauche de la constante.
— La Figure 9 représente une solution possible où on n’autorise pas la présence
d’un ou plusieurs zéros à gauche de la constante.
2. L’ensemble des chaînes composées de lettres, de chiffres et de tirets. Elles ne
peuvent ni commencer, ni finir par un tiret et ne contiennent pas deux tirets
consécutifs.
Soitc= [0−9]etl= [a−zA−Z]. L’automate est donné par la Figure 10,
il accepte la chaîne vide. Dans le cas où la chaîne vide ne devrait pas être
acceptée par l’automate, on peut rendre l’étatq0 non final.
3. L’ensemble de toutes les chaînes de0et de1telles que chaque0soit immé-
diatement suivi par au moins un1.
Les automates des Figures 11 et 12 représentent deux solutions possibles. Le
premier accepte la chaîne vide, alors que le deuxième l’interdit.
4. L’ensemble de chaînes formées de lettres telles que les consonnes sont séparées
par des voyelles (pas de consonnes consécutives).
On représente parlcetlvles lettres consonnes et les voyelles, respectivement.
Les automates des Figures 13 et 14 représentent deux solutions possibles. Le
premier accepte la chaîne vide, alors que le deuxième l’interdit.2 Figure6 – Automate reconnaissantL(E5 )
Figure7 – Automate reconnaissantL(E5 )
Exercice 3Soit l’automateAdonnée par la Figure 15.
1. Trouver l’automate simple déterministeCéquivalent àAtel queL(A) =L(C)
La Table 1 représente la table de transition de l’automateA: Les calculs
de l’algorithme de conversion sont résumés dans la Table 2, qui représente
également la table de transition de l’automateCavant ré-numérotation desétats. La Table 3, représente la table de transition de l’automate obtenu après ré-
numérotation des états. Il suffit de ré-numéroter les états dans l’ordre en com-
Étatabc→S 0S 3S 2S 2S 1S 2S 2∗S 2S 1S 3S 1
Table1 – Table de transition de l’automateA3 Figure8 –
Exercice 2: Solution 2mençant par l’indice0. Ici j’ai préféré garder le plus possible les mêmes indices
que l’automate d’origine. La Figure 16 représente le diagramme de transition
de l’automateC.
Exercice 4Soit l’automate A donné par la Figure 17.
1. Trouver un automate déterministeCéquivalent àA, tel queL(A) =L(C)
2. TrouverBdéterministe tel queL(B) =M iroir(L(A))Étatabc →epsf er({S0 }) =S0 epsf er({S3 }) =S3 epsf er({S2 }) =S2 epsf er({S2 }) =S2 S3 epsf er({S1 }) =S1 , S2 ∗S2 epsf er({S1 }) =S1 , S2 ∗S1 , S2 epsf er({S1 }) =S1 , S2 epsf er({S2 }) =S2 Table2 – Table de transition de l’automateC4 Figure10 – Automate exercice 2-2
Figure11 –
Exercice 2 : Solution 1État abc →q0 q3 q2 q2 q3 q1 ∗q2 q1 ∗q1 q1 q2 Table3 – Table de transition de l’automateCaprès ré-numérotation des états