Théorie des langages : Correction td 2 : automates finis
Télécharger PDFUniversité Sidi Mohamed Ben Abdellah École Nationale des Sciences Appliquées Année Universitaire : 2019-2020 Module : Théorie des langages Filière : GINF - 1
ère Année Professeur : 1 Correction - TD 2 : Automates Finis
Exercice 1On considère deux automates 퐴
1 et 퐴
2 sur l’alphabet {푎,푏 }
. 1. 푎 → état 1,
푎푏 → état 2,
푎푏푏 → état 2,
푎푏푏푎 → état 2,
휀 → état 0 2. Les mots reconnus par l’automate 퐴
1 sont 푎푏, 푎푏푏 et 푎푏푏푎 3. Lorsque la lecture du mot 푎푎푏 l’automate 퐴
1 sera bloquée dans l’état 1 4. 푎푏푎2 푏 → oui,푎 2푏푎 2
푏 → non,푎푏 4
→ oui,푏 3푎 2
→ non 5. 푏3 푎2 → état 1 6. S’il n’a lu aucun 푎, l’automate 퐴
2 se trouve toujours dans état 0 7. l’automate 퐴
2 arrive à l’état final 2 si le mot contient au moins un 푎푏 8. 퐿( 퐴1 )= {푎 }∙ {푏 }∙ {{ 푎} ∪{ 푏} }∗ ou 퐿( 퐴1 )= {
푎푏푤 / 푤∈{ 푎,푏} ∗} 퐿( 퐴2 )= {푏 }∗ ∙{ 푎} ∙{ 푎} ∗∙ {푏 }∙ {{ 푎} ∪{ 푏} }∗ ou 퐿( 퐴2 )= {푏 푛푎푎 푚
푏푤 / 푤∈{ 푎,푏} ∗
,푛≥0,푚≥0} 9. - Miroir des 퐴
1 : - Miroir des 퐴
2 : 10. - Complémentaire de 퐴
1 : - Complémentaire de 퐴
2 :
Exercice 22 퐿1 = {휀 }
퐿2 = {휀,푎,푎푏 }
퐿3 = {푎 푖
,푖 ≥ 0} 퐿4 = {푎 푖 푏푗 푐
2푘 ,푘,푖 ≥ 0,푗 > 1} 퐿5 = Les mots de {푎,푏 }
∗ ne contenant pas la chaîne 푏푏푎. 퐿6 =
{ 휔,휔 ∈ {푎,푏 }
∗ ,|휔|푎 =[2−3]} 퐿7 = Les entiers naturels multiples de 2. 퐿8 = 푎+푏∗ 퐿9 = {푎푏 }{푎,푐 }{푏 }+ 3 퐿10 = (( 푎
+ 푏푎∗ )+ + (푎푏 +푏 ∗) )
푎푏 ≡ (( 푎
+ 푏푎∗ )+ + (푎푏 +) )
푎푏 퐿11 = 푎(푎푏 + 푏∗ )(푎푏푎)∗ 퐿12 = (푎푏+푎)∗ +(푎푏푎∗ 푏+푏푎)+ Remarque : Vous pouvez utiliser l’algorithme de déterminisation pour convertir l’AFN de 퐿10 , 퐿11 et 퐿
12 en l’AFD correspondent. 4
Exercice 3- On peut avoir 4 types de déplacements (i.e. transitions) : o H : l’homme traverse tout seul o HC : l’homme traverse avec la chèvre o HL : l’homme traverse avec le loup o HX : l’homme traverse le choux - L’AFN Remarque: les états dans ce cas indiquent les entités situées de chaque côté de la rivière à certain moment.
Exercice 41. Les mots appartiennent à 퐿 : 푎푎 Les mots n’appartiennent pas à 퐿 : 푎푏푎, 푎푎푏푏푎푏, 푎푏푏푏푏푏 2. 퐿={ 푤∈{ 푎,푏} ∗ / |푤 |푎 =| 푤| 푏
+2(2푘+1),푘∈ℤ} 3. AFD qui reconnaît les mots de 퐿 : ( {푁,퐸,푆,푂 }
,{푎,푏},훿,푁,{푆}) avec 훿 définie par : 5
Exercice 5- AFN : - Le langage associe : 퐿={ {푎푏 }∪ {휀 }} ∙{ 푎} +∪ {{ 푎} ∪{ 푏} }∗ ∙{ 푏}
Exercice 6- AFN : - Table de transitions [0-9] [1-9] + - , 0 1 1 1 3 2
2 {2,3}3 4 4 4 55
Exercice 7- AFN : 6
Exercice 81. L’expression régulière : 푎푏푎∗ 푏 2. On peut exprimer l’ensemble des mots de {푎,푏}
∗ proches de 퐿 par ces cinq expressions régulières : 푎푏푎∗ 푏, 푎푏푎∗ 푎, 푎푏푎∗ 푏푎∗ 푏, 푎푎푎∗ 푏, et 푏푏푎∗ 푏. Alors, tout mot généré par l'une de ces expressions régulières est proche de 퐿. Par conséquent, l’ensemble des mots de {푎,푏}
∗ proches de 퐿 peut être représenté par l’expression régulière : 푎푏푎∗ 푏+푎푏푎∗ 푎+푎푏푎∗ 푏푎∗ 푏+푎푎푎∗ 푏+푏푏푎 ∗
푏. Il suffit maintenant de construire un AFN corresponde a cette dernière : Après la simplification :