Title °TD compilation SMI5 FSAC CASABLANCA.pdf ✅

Université Hassan II De Casablanca Année universitaire 2020/2021 Faculté des sciences AIN Chock Filière SMI Département des mathématiques et informatique Semestre S5 Pr Errais Mohammed Module Compilation TD 1 : Expressions régulières et automates finis Exercice I : Donner l’expression régulières des langages suivants : 1) Le langage L des mots qui commencent par a et se terminent par bc sur V= {a, b, c}. 2) Langage L des mots binaires qui acceptent la division sur 2 et n’admettent pas des 0 unités au début. 3) Le langage L des nombres naturels signés. 4) Des identificateurs sous le langage C. 5) Des entiers naturels acceptant la division sur 5. 6) Des nombres naturels appartenant à l’intervalle [-999,1000]. 7) Des mots qui comportent au moins deux occurrences de la sous chaines ‘ab’ sur V={a, b , c} Exercice II Retrouver les expressions régulières des langages à partir des automates suivants : 1) 2) 3) Exercice III Donner l’expression régulière et l’automate fini engendré par les langages : 1) L1 le langage des mots binaires qui commencent par 1, incluent au moins une occurrence de la chaine 101 et acceptent la division sur 8. 2) L2 le langage des nombre décimales appartenant à l’intervalle [1,500] sur V={,0,1,2,3,4,5}. 3) L3 le langage des mots qui commencent par a et ne se terminent pas par b ou c sur V={a,b,c}
Université Hassan II De Casablanca Année universitaire 2020/2021 Faculté des sciences AIN Chock Filière SMI Département des mathématiques et informatique Semestre S5 Module Compilation TD 1 : Expressions régulières et automates finis Solution : 20/11/2020 Exercice I 1) Le langage L des mots sur V={a,b,c} qui commencent par a et se terminent par bc. a.bc a X. bc => tel que peut prendre n’importe quel mot a.(a+b+c)*.bc 2) L le langage sur V= {0,1}. L2 = L22 et L21 L22 : Acceptent la division sur 2  le mot doit se terminer par 0 : (1+0)*.0 L21 : Le langage des mots qui n’acceptent pas 0 au début :1.(1+0)*+0 L = (1.(1+0)*+0).(1+0)*.0) E(L)=(1.(1+0)*.0) + 0 2) L le langage des naturels signés V= {0,1,2,3,4,5,6,7,8,9,-,+} ?(+|-) [0-9]+ 3) Des entiers naturels acceptant la division sur 5. [0-9]*(5+0) 4) Des nombres naturels appartenant à l’intervalle [-999,1000]. L1 : les entiers entre -999 et 0 L2 : les entiers entre 0 et 1000 L1 : - [0-9] -[1-9][0-9] -[1-9][0-9][0-9] -([0-9]+[1-9][0-9]+[1-9][0-9][0-9]) L2 : [0-9] [1-9][0-9] [1-9][0-9][0-9] 1000 [0-9]+[1-9][0-9]+[1-9][0-9][0-9]+1000 L : -([0-9]+[1-9][0-9]+[1-9][0-9][0-9]) | [0-9]+[1-9][0-9]+[1-9][0-9][0-9] | 1000 5) Des mots qui comportent au moins deux occurrences de la sous chaines ‘ab’ sur V={a, b , c} x.ab X ab.X (a+b+c)*.ab.(a+b+c)*.ab.(a+b+c)*
Université Hassan II De Casablanca Année universitaire 2020/2021 Faculté des sciences AIN Chock Filière SMI Département des mathématiques et informatique Semestre S5 6) Des identificateurs sous le langage C. V={a,b,c , ..,z , A, B,C ... Z, _, 0,1,2...9} ([a-z] | [A-Z] | _). ([a-z] | [A-Z]|[0-9]|_)* Exercice II 1) V= {a,b} a b*.a.(a+b)* Remarque : Comme une règle générale pour chaque transition locale ça se traduit par *. 2) (b*.a.b*.a)* V= {a,b} 3) b*.a.a*.b.a.(a+b)*  b*.a+.ba(a+b)*
Université Hassan II De Casablanca Année universitaire 2020/2021 Faculté des sciences AIN Chock Filière SMI Département des mathématiques et informatique Semestre S5 Module Compilation TD 1 : Expressions régulières et automates finis Solution : 27/11/2020 Exercice III Donner l’expression régulière et l’automate fini engendré par les langages : 1) L1 le langage des mots binaires qui commencent par 1, incluent au moins une occurrence de la chaine 101 et acceptent la division sur 8. L11 : le langage des mots binaires qui commencent par 1 : 1.X L12 : une occurrence de la chaine 101 : X101X L13 : accepte la division sur 8. : X.000 e(L1) : 1.(1+0)*.101.(1+0)*.000 2) L2 le langage des nombre décimales appartenant à l’intervalle [1,500] sur V={0,1,2,3,4,5}. L2 selon trois langages L21 : les entiers qui se compose d’un seul chiffre : [1-5] L22 : les entiers qui se composent de deux chiffres [1-5][0-5] L23 : de trois chiffres : [1-4][0-5][0-5] | 500 E(L2) : [1-5] + [1-5][0-5] + [1-4][0-5][0-5] + 500