Remerciez-le!

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

Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des La

Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 1 - Université Mouloud MAMMERI de Tizi-Ouzou Année universitaire : 2015/2016 Faculté de génie électrique et informatique 2ième année Licence-Informatique Département d’informatique module : Théorie des langages CORRIGÉ ABREGÉ DE LA SÉRIE D’EXERCICES no 2 de ThL par : S. Khemliche, M.S. Habet, Y. Yesli EXERCICE 1 : a) L1 = { w  {a, b}* / w = anbma ou w = ban ; n, m ≥ 1 } : b a b a a a b a b) L2 = { w  {0, 1}* / w = 1(101)n00 ou w = 0(010)n11, n≥0 } : 0 1 1 0 1 0 0 1 1 0 0 1 q0 q1 q2 q3 q4 q5 q0 q1 q2 q3 q4 q5 q6 q7 q9 q8 Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 2 - c) L3 = { w  {a, b}* / |w| ≡ 0 [6] } : a, b a, b a, b a, b a, b a, b d) L4 = { w  {0, 1}* / w ne contient pas la sous chaîne «010» } : 1 0 0 1 1 e) L5 = ensemble des mots de {0, 1}* représentant les nombres divisibles par 3 (dans le système de numération binaire naturel) : 0 1 0 1 1 0 q0 q1 q2 q3 q4 q5 q2 q1 q0 r0 r1 r2 Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 3 - EXERCICE 2 : 1) L’automate A : 0 0 0 1 1 1 1 L’automate B : a a a a b b b b b a 2) Grammaire régulière à droite équivalente à A : GA = ({0, 1}, {S, A, B}, S, PA), où PA contient les règles : S → 0S | 0A | 1B ; A → 0A | 1B | ε ; B → 1S | 1B | ε Grammaire régulière à droite équivalente à B : GB = ({a, b}, {S, A, B, C}, S, PB), où PB contient les règles : S → aS | aA | bB ; A → bB | aC | ε ; B → bA | aB | bC ; C → aA | bB 3) Table de transition de l’automate déterministe équivalent à A : (les états soulignés sont des états finaux) 0 1 <S0> = q0 <S0,S1> <S2> <S0,S1> = q1 <S0,S1> <S2> <S2> = q2 / <S0,S2> <S0,S2> = q3 <S0,S1> <S0,S2> S0 S1 S2 S3 S2 S0 S1 Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 4 - L’automate déterministe équivalent à A : 0 0 0 1 1 1 1 Table de transition de l’automate déterministe équivalent à B : a b <S0> = q0 <S0,S1> <S2> <S0,S1> = q1 <S0,S1,S3> <S2> <S0,S1,S3> = q2 <S0,S1,S3> <S2> <S2> = q3 <S2> <S1,S3> <S1,S3> = q4 <S1,S3> <S2> L’automate déterministe équivalent à B : a a a b b a b b b a EXERCICE 3 : D’abord on transforme l’automate généralisé A en automate partiellement généralisé Ap en décomposant les transitions qui se font sur des mots. C’est le cas, pour A, de la transition (ab , S2 , S2) ; pour la décomposer on ajoute un nouvel état S6 et on la remplace par les transitions (a , S2 , S6) et (b , S6 , S2). Ensuite, à partir de l’automate partiellement généralisé Ap, on construit l’automate simple As en éliminant les ε-transitions (qu’on appelle aussi les transitions spontanées) suivant les règles : ▪ si (ε , Si , Sj) ∈ I et Sj est un état final alors Si deviendra lui aussi état final ; q0 q1 q2 q3 q0 q3 q1 q2 q4 Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 5 - ▪ si (ε , Si , Sj) et (a , Sj , Sk) ∈ I alors ajouter la transition : (a , Si , Sk) à I. À la fin des ajouts, éliminer la transition (ε , Si , Sj) de I. Ainsi, on obtient l’automate As suivant : a b a a b a a a b Remarque : On n’a pas représenté l’état S1 car il est devenu inaccessible (c'est-à-dire qu’on ne peut pas l’atteindre à partir de l’état initial S0) ; on l’a donc supprimé de As. EXERCICE 4 : 1) On construit d’abord l’automate simple As équivalent à A, en procédant de la même manière que dans l’exercice 3 précédent. On obtient l’automate simple (non déterministe) As suivant : 0 0 0 0 0 0 0 1, 0 0 0 Ensuite, on transforme As en automate déterministe, en procédant de la même manière que dans l’exercice 2. S2 S0 S3 S4 S5 S6 S0 S4 S1 S3 S2 Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 6 - On obtient l’automate déterministe Ad suivant : 0 0 0 1 1 0 2) Pour obtenir l’automate du complémentaire de L(A) (c'est-à-dire du complémentaire de L(Ad), car A et Ad sont équivalents), on procède comme suit : I) on prend l’automate simple déterministe Ad, obtenu en 1) ; II) on complète Ad : on ajoute un état puits – non final – qp, qu’on raccorde aux états qui on des transitions manquantes ( ici, le raccordement se fait en ajoutant les transitions (1, q0 , qp) et (1 , q3 , qp) – ne pas oublier les transitions (0, qp , qp) et (1, qp , qp) ) ; III) on inverse les états finaux et non finaux : les états non finaux vont devenir finaux et vice versa. On obtient ainsi : 0 0 0 1 1 1 1 0, 1 0 EXERCICE 5 : On va traiter les deux questions 1) et 2) pour les deux grammaires g1 et g2. Pour construire un automate équivalent à une grammaire régulière, on procède comme suit : i-) on associe à chaque non terminal de la grammaire, un état de l’automate. L’état associé à l’axiome sera l’état initial de l’automate ; ii-) à toute règle de production A → ε de la grammaire, l’état associé au non terminal A sera final ; q1 q3 q2 q0 q0 qp q3 q2 q1 Corrigé abrégé de la Série n° 2 U.M.M.T.O – année : 2015/2016 de Théorie des Langages - 7 - iii-) à toute règle A → wB, où w est un mot, on ajoutera la transition (w , EA , EB) dans l’automate (EA et EB sont les états associés à A et B respectivement) ; iv-) à toute règle A → w, où w est un mot, on ajoutera la transition (w , EA , F) dans l’automate (EA est l’état associé à A, F est un nouvel état final). Ainsi, en appliquant les étapes i-)..iv-), avec la grammaire g1 : g1 = <π, N1, S, P1> où π = {a, b, c} ; N1 = {S, A, B} ; P1 = { S → abS | bA | ε ; A → bB | B ; B → aB | b | cA } ; on obtient l’automate A1 suivant, qui est équivalent à g1 : A1 = < V , S , F , S0 , I > où V = {a, b, c} ; S = {S0 , S1 , S2, S3} ; F = {S0, S3} ; S0 état initial I = { (ab , S0 , S0) ; (b , S0 , S1) ; (b , S1 , S2) ; (ε , S1 , S2) ; (a , S2 , S2) ; (b , S2 , S3) ; (c , S2 , S1) } ; On transforme ensuite cet automate généralisé A1 en automate simple : - automate partiellement généralisé : A1p = < V , S’ , F , S0 , I > où V = {a, b, c} ; S’ = {S0 , S1 , S2, S3, S4} ; F = {S0, S3} ; S0 état initial I = { (a , S0 , S4) ; (b , S4 , S0) ; (b , S0 , S1) ; (b , S1 , S2) ; (ε , S1 , S2) ; (a , S2 , S2) ; (b , S2 , S3) ; (c , S2 , S1) } ; - automate simple : A1s = < V , S’ , F , S0 , I > où V = {a, b, c} ; S’ = {S0 , S1 , S2, S3, S4} ; F = {S0, S3} ; S0 état initial I = { (a , S0 , S4) ; (b , S4 , S0) ; (b , S0 , S1) ; (b , S1 , S2) uploads/Philosophie/ thl-sol-serie2-2016-pdf.pdf