Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

ISG, Année Universitaire : 2012/2013 Théorie des Langages et des Automates : (2

ISG, Année Universitaire : 2012/2013 Théorie des Langages et des Automates : (2ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI et Mme Kaothar NOUIRA FERCHICHI - TD : M Badr MEFTAHI _________________________________________________________________________________________________________________ Série N°2 : Langages Réguliers Spécifications par des expressions régulières et Reconnaissance par des AEF Correction Exercice 1 1) La démonstration se fait en revenant à la définition d'une expression régulière, sachant que tout langage régulier peut être exprimé par une expression régulière. 2) Décrivez en langage naturel les langages réguliers suivants : L1={(a ∪ b)* aa (a ∪ b)*} : les mots définis sur S={a,b} et tel qu'ils contiennent au moins la sous chaine aa L2={((a ∪ c) b*d) }: les mots définis sur S={a,b,c,d} et tel qu'ils commencent par a ou c suvi par zéro ou plusieurs b et finissant par d L3={(a ∪ ba ∪ bba)* ( ε ∪ b ∪ bb)} : les mots définis sur S={a,b} et tel qu'ils ne contiennent pas 3 b successifs L4={(a ∪ b)* }: les mots définis sur S={a,b} pouvant être la chaîne vide ou n'importe quelle chaine avec des a et/ou des b ou les deux à la fois (avec des a et des b) 3) Proposer pour chaque expression régulière, une autre expression régulière équivalente (a ∪ b)* équivalent à (b ∪ a)* (a*)* = a* a ∪ (b ∪ a)= (a ∪ b) ∪ a 4) On sait que ces langages sont réguliers, les décrire yèpar des expressions régulières : L1 = {ab} expression régulière ab L2 = {anbam, n>=0, m>=0} expression régulière a*ba* L3 = {an, n>2} expression régulière aaaa* Exercice 2 1) L1 = La conjugaison du verbe regarder au futur simple. 2) L2 = Les heures sur 12h de la forme hh H mm. Exercice 3 L1 = {e, a, b, ab} ð ER1 = e | a | b | ab L2 = {bn / n>=2, n étant un entier} ð ER2 = bbb* ISG, Année Universitaire : 2012/2013 Théorie des Langages et des Automates : (2ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI et Mme Kaothar NOUIRA FERCHICHI - TD : M Badr MEFTAHI L3 = {wÎ{a,b}*, tel que w contient seulement 3b, le reste c'est des a's} ð ER3 = a*ba*ba*ba* L4 = {wÎ{a,b}*, tel que w contient un nombre de a divisible par 3} ð ER4 = (b*ab*ab*ab*)* È b* L5 = {wÎ{a,b}*, tel que w contient un nombre paire de a} ð ER5 = (b*(ab*a)*b*)* L6 = {wÎ{a,b}*, tel que w contient un nombre impaire de b} ð ER6 = a*b (a*(ba*b)*a*)* L7 = {wÎå*, w ne contient pas 3b consécutifs} ð ER7 = (a È ba È bba)* (e È b È bb) L8 = {wÎ{a,b}*, tel que w contient la sous chaîne aaa ou la sous chaîne bbb mais pas les deux en même temps} On remarque que L8 = L9 È L10 avec L9 = {wÎ{a,b}*, tel que w contient la sous chaîne aaa mais pas la sous chaîne bbb} L10 = {wÎ{a,b}*, tel que w contient la sous chaîne bbb mais pas la sous chaîne aaa} ER9 = (a È ba È bba)*(e ÈbÈbb) aaa (a È ba È bba)*(e ÈbÈbb) ER10 = (b È ab È aab)*(e ÈaÈaa) bbb (b È ab È aab)*(e ÈaÈaa) ER8 = ER9 È ER10 ð ER8 = (a È ba È bba)*(e ÈbÈbb) aaa (a È ba È bba)*(e ÈbÈbb) È (b È ab È aab)* (e ÈaÈaa) bbb (b È ab È aab)*(e ÈaÈaa) Exercice 4 1) a - ER1 = e | a | b | ab 1 2 4 3 a b b ISG, Année Universitaire : 2012/2013 Théorie des Langages et des Automates : (2ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI et Mme Kaothar NOUIRA FERCHICHI - TD : M Badr MEFTAHI b - ER2 = bbb* c - ER3 = a*ba*ba*ba* d - ER5 = (b*(ab*a)*b*)* Ou encore 1 2 3 b b b b b b a a a a 1 2 3 4 1 2 3 b b b a a a 1 2 3 b b b a a ε ISG, Année Universitaire : 2012/2013 Théorie des Langages et des Automates : (2ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI et Mme Kaothar NOUIRA FERCHICHI - TD : M Badr MEFTAHI 2)a- b- c- 1 2 4 3 a b b a,b ,b a,b ,b a,b ,b a M 1 a a a b 2 M 3 b a,b ,b b b b b a a a a 1 2 3 4 ISG, Année Universitaire : 2012/2013 Théorie des Langages et des Automates : (2ème année IAG, semestre 4) Cours : Mme Lamia EL ABED JILANI et Mme Kaothar NOUIRA FERCHICHI - TD : M Badr MEFTAHI d- Pour la première proposition l’automate est déjà complet. M a,b ,b b uploads/s3/ tlaserie-2-correc.pdf