ࡱ> }~g jbjb jF]vvvd8y8y8y8yyz\8y4~߻]______,2uv=K߻==24~= Pv] wx=]@9 Wv]0}R8y8y3h9$ Cours dinformatique Introduction la thorie des langages J. Chauch, M. Lafourcade Octobre 1998 Table des matires  TM \o "1-3" Introduction  RENVOIPAGE _Toc434316450 \h 5 Vocabulaires, mots, langages  RENVOIPAGE _Toc434316451 \h 7 1. Dfinitions de base  RENVOIPAGE _Toc434316452 \h 8 1.1. Vocabulaire  RENVOIPAGE _Toc434316453 \h 8 1.2. Mot  RENVOIPAGE _Toc434316454 \h 8 1.3. Langage  RENVOIPAGE _Toc434316455 \h 8 1.4. Codage  RENVOIPAGE _Toc434316456 \h 9 1.5. Algorithme  RENVOIPAGE _Toc434316457 \h 11 2. Oprations sur les mots  RENVOIPAGE _Toc434316458 \h 14 2.1. Prfixe  RENVOIPAGE _Toc434316459 \h 14 2.2. Suffixe  RENVOIPAGE _Toc434316460 \h 14 2.3. Infixe  RENVOIPAGE _Toc434316461 \h 14 2.4. Image miroir  RENVOIPAGE _Toc434316462 \h 14 3. Oprations sur les langages  RENVOIPAGE _Toc434316463 \h 15 3.1. Oprations ensemblistes  RENVOIPAGE _Toc434316464 \h 15 3.2. Concatnation  RENVOIPAGE _Toc434316465 \h 16 3.3. Opration puissance  RENVOIPAGE _Toc434316466 \h 17 3.4. Opration * (toile de Kleene)  RENVOIPAGE _Toc434316467 \h 18 4. Expressions rgulires  RENVOIPAGE _Toc434316468 \h 18 4.1. Dfinition en intention et dfinition en extension  RENVOIPAGE _Toc434316469 \h 18 4.2. Dfinition rcursive  RENVOIPAGE _Toc434316470 \h 19 4.3. Exemples  RENVOIPAGE _Toc434316471 \h 19 4.4. Lois algbriques sur les expressions rgulires  RENVOIPAGE _Toc434316472 \h 20 4.5. Quelques proprits intressantes  RENVOIPAGE _Toc434316473 \h 22 4.6. Dfinition arborescente  RENVOIPAGE _Toc434316474 \h 23 Conclusion  RENVOIPAGE _Toc434316475 \h 25 Exercices  RENVOIPAGE _Toc434316476 \h 25 Automates dtats finis et langages rguliers  RENVOIPAGE _Toc434316477 \h Error! Bookmark not defined. 1. Automates dtats finis  RENVOIPAGE _Toc434316478 \h Error! Bookmark not defined. 1.1. Dfinition informelle  RENVOIPAGE _Toc434316479 \h Error! Bookmark not defined. 1.2. Notations  RENVOIPAGE _Toc434316480 \h Error! Bookmark not defined. 1.3. Reconnaissance dun mot  RENVOIPAGE _Toc434316481 \h Error! Bookmark not defined. 1.4. Dfinition formelle des Automates Finis Dterministes (AFD)  RENVOIPAGE _Toc434316482 \h Error! Bookmark not defined. 1.5. Dfinition formelle des automates finis non dterministes (AFN)  RENVOIPAGE _Toc434316483 \h Error! Bookmark not defined. 1.5. Automate avec (-transition  RENVOIPAGE _Toc434316484 \h Error! Bookmark not defined. 1.7. quivalences dautomates  RENVOIPAGE _Toc434316485 \h Error! Bookmark not defined. 2. Passage dune expression rgulire vers un automate  RENVOIPAGE _Toc434316486 \h Error! Bookmark not defined. 2.1. Proprit  RENVOIPAGE _Toc434316487 \h Error! Bookmark not defined. 2.2. Cas de base  RENVOIPAGE _Toc434316488 \h Error! Bookmark not defined. 2.2. Rcurrence  RENVOIPAGE _Toc434316489 \h Error! Bookmark not defined. 2.4. limination des (-transitions  RENVOIPAGE _Toc434316490 \h Error! Bookmark not defined. 3. Passage dun automate vers une expression rgulire  RENVOIPAGE _Toc434316491 \h Error! Bookmark not defined. 3.1. Par rduction dautomates  RENVOIPAGE _Toc434316492 \h Error! Bookmark not defined. 3.2. Par rsolution dquations  RENVOIPAGE _Toc434316493 \h Error! Bookmark not defined. 4. Dterminisation & Minimisation  RENVOIPAGE _Toc434316494 \h Error! Bookmark not defined. 4.1. Mthode de dterminisation  RENVOIPAGE _Toc434316495 \h Error! Bookmark not defined. 4.3. Relation dquivalence sur les langages rguliers  RENVOIPAGE _Toc434316496 \h Error! Bookmark not defined. 5. Autres oprations sur les automates  RENVOIPAGE _Toc434316497 \h Error! Bookmark not defined. 5.1. Automate complmentaire A  RENVOIPAGE _Toc434316498 \h Error! Bookmark not defined. 5.2. Automate miroir A~  RENVOIPAGE _Toc434316499 \h Error! Bookmark not defined. 5.3. Intersection de deux automates  RENVOIPAGE _Toc434316500 \h Error! Bookmark not defined. Exercices  RENVOIPAGE _Toc434316501 \h Error! Bookmark not defined.  Introduction Chapitre 1 Vocabulaires, mots, langages TM \o "1-3" \n \p " "  1.1 Dfinitions de base Vocabulaire Mot Langage Codage Algorithme 1.2 Oprations sur les mots Prfixe Suffixe Infixe . Image miroir 1.3 Oprations sur les langages Oprations ensemblistes Concatnation Opration puissance Opration * (toile de Kleene) 1.4 Expressions rgulires Dfinition en intention et dfinition en extension Dfinition rcursive Exemples Lois algbriques sur les expressions rgulires Quelques proprits intressantes Dfinition arborescente 1.5 Conclusion  Dans ce chapitre, nous prsentons les concepts de base ncessaire la comprhension du reste du cours. Nous prsentons les notions de vocabulaire, de mots et de langages. Nous illustrons comment tout traitement informatique est entour de phases de dcodage et de codage dont la nature est un traitement sur un (ou plusieurs) langages. Les oprations de base sur les langages seront prsentes ainsi que la classe des langages rguliers. Les manipulations sur les expressions rgulires seront illustres. Nous supposons connues les dfinitions de base de la thorie des ensembles et de celle des nombres. 1. Dfinitions de base 1.1. Vocabulaire Un vocabulaire est un ensemble fini de signes. Par exemple, il peut sagir dun alphabet (latin, cyrillique, arabe), dun syllabaire (japonais), etc. ( Par exemple, on notera: V = {a, b, c} le vocabulaire V compos des lettre a, b et c. On peut aussi avoir: Vromain = {A, B, C, D, E, F, & Z} Vthai = {, , , , " , , , , , "!, & } Vnpalais = { , ' , - ,  , $ , % ,  , 7 , / , & } Vmorse = {(, ( } Vchat = {le, petit, chat, boit, du, lait } ( 1.2. Mot Sur cet alphabet, on construit des mots l aide de l opration de concatnation. Cette opration est note par le signe: . Soient u, v des mots, alors u . v est un mot. ( Par exemple: a.b ( ab ab . c ( abc a . bc ( abc ( La longueur dun mot est le nombre dlments du vocabulaire le composant. ( Par exemple, le mot ab a une longueur gale 2 ( ( est le mot vide. Sa longueur est nulle, car il nest compos daucun lment du vocabulaire. Soient u et v deux mots de longueur lu et lv alors la longueur de u . v est lu+lv. On peut dfinir la fonction longueur par rcurrence: 1.3. Langage Soit V un vocabulaire. Lensemble des mots possibles sur V est not V*. ( Par exemple: V = {a, b} V* = {(, a, b, aa, ab, ba, bb, aaa, aab, aba, abb, baa, bab, bba, } ( On note ( le langage vide (il ne contient aucun mot). Le mot vide ( est bien un mot ne pas confondre avec (. V* est un monode. Un monode est un ensemble muni dune opration associative et possdant un lment neutre. Ici, lopration associative est la concatnation . et llment neutre est (. ( Par exemple: V = {a, b} a.(a.b) = (a.a).b et dune faon gnrale: si u ( V* et x ( V alors x.u = u.x et appartient V* si u, v, w ( V* alors u.(v.w) = (u.v). w et appartient V* de plus: a.( = (.a = a et dune faon gnrale: si u ( V* alors u.( = (.u = u ( On notera V+, lensemble V* priv de (. Autrement dit, nous avons V* = V+ ( {(}. Intuitivement, V+ est lensemble de tous les mots possibles sur V et dont la taille est suprieure ou gale 1. Un langage est dfini sur un vocabulaire V et constitue un sous-ensemble de V*. ( Par exemple, une langue utilisant lalphabet latin, comme le Franais, est un sous-ensemble des mots possibles sur le vocabulaire V={a, , z, A, , Z, ,?, }. Lensemble des entiers L est reprsent par le langage dfini sur V={0, 9} o aucun mot de commence par 0 part 0 lui-mme. De faon plus formelle, L = {0} ( ensemble des mots de V+ ne commenant pas par 0. ( 1.4. Codage Soit deux vocabulaires V1 et V2. Un codage est une fonction de V1* dans V2*. Le codage peut sappliquer sur le vocabulaire et tre tendu au langage. Dans ce cas, il sagit dun codage fixe.   Un codage f est dcodable que si f est une fonction injective. Une fonction f est injective si tout lment de limage de f a un antcdent unique. ( Par exemple, soit V1 = {a, b, c} et V2 = {1, 2, 3} et les rgles de codage suivantes: a ( 0 b ( 1 c ( 2 Alors le mot bab est cod 101. Il est facile de voir que tout mot de V1 est cod de faon unique. Ce codage est donc dcodable. On remarquera que dans ce cas f tant bijective, la fonction inverse f-1 est aussi un codage dcodable. ( Il existe des fonctions de codage partir desquelles on ne peut pas dduire facilement la fonction de dcodage. Cette fonction de dcodage nest en fait connue que par les personnes autorise dcoder les messages. Par contre, toute personne peut coder un message. De telles fonctions sont utilises pour le cryptage de donnes. Dune faon gnrale, le codage et le dcodage constituent des oprations fondamentales du traitement de linformation. ( Par exemple, lopration raliser est la somme de deux nombres a laide dun additionneur binaire. Le vocabulaire est V={0,,9,+}. Le mot trait est par exemple: 12+4. Le code de 12 est 1100. Le code de + est 111111. Le code de 4 est 0100. Le rsultat du traitement (que nous nexplicitons pas ici) est 10000. Le dcodage de 10000 donne 16. ( Exercice le codage Morse La table ci-dessous dcrit un codage de V1* sur V2*. En Morse, un message se termine toujours par le symbole de fin de message #. Une pause (note /) est toujours insre entre chaque caractre transmis sous forme code. cCodeSoncCodeSonA. _didahU. . _dididahB_ . . .dahdididitV. . . _didididahC_ . _ .dahdidahditW. _ _didahdahD_ . .dahdiditX_ . . _dahdididahE.ditY_ . _ _dahdidahdahF. . _ .dididahditZ_ _ . .dahdahdiditG_ _ .dahdahdit1. _ _ _ _didahdahdahdahH. . . .didididit2. . _ _ _dididahdahdahI. .didit3. . . _ _didididahdahJ. _ _ _didahdahdah4. . . . _dididididahK_ . _dahdidah5. . . . .dididididitL. _ . .didahdidit6_ . . . .dahdidididitM_ _dahdah7_ _ . . .dahdahdididitN_ .dahdit8_ _ _ . .dahdahdahdiditO_ _ _dahdahdah9_ _ _ _ .dahdahdahdahditP. _ _ .didahdahdit0_ _ _ _ _dahdahdahdahdahQ_ _ . _dahdahdidah.. _ . _ . _didahdidahdidahR. _ .didahdit,_ _ . . _ _dahdahdididahdahS. . .dididit?. . _ _ . .dididahdahdiditT_dah(. _ . _ .Didahdidahdit Explicitez V1 et V2. Que peut-on dire des mots de V1* et des mots de V2*? Ce codage est-il dcodable? Justifier votre rponse. Un apprenti tlgraphiste relev le message suivant, en oubliant dindiquer les pauses: . . . _ _ _ . . . _ . . _ . _ _ . . . _ . _ . _ . _ . _ _ _ . . _ . _ . . . . _ . _ . Pouvez-vous laider le transcrire? Comment sy prendrait-on avec une machine? ( Dune faon gnrale, un traitement informatique consiste rsoudre les points suivants: Reconnaissance des mots (cest--dire encore codage des mots); Traitement de ces mots sous forme code; Dcodage du rsultat. Ici, nous avons pris le point de vue humain. Du point de vue de la machine nous aurions: Reconnaissance des mots (cest--dire dcodage des mots); Traitement de ces mots sous forme dcode; Encodage du rsultat. Retenons simplement que linformatique constitue essentiellement une question de: Codage Traitement Dcodage 1.5. Algorithme Un algorithme est une suite finie doprations permettant de rsoudre un problme (cest--dire de rpondre une question). Exercice: Algorithme dEuclide permettant de trouver le pgcd (plus grand dnominateur commun) de deux nombres. Rponses: Les proprits du pgcd de u et v sont: Si u ( v alors u = vq + r avec r >0 Si r = 0 alors pgcd(u, v) = v Sinon (cest--dire si u < v), pgcd (u, v) = pgcd(v, r) car un diviseur de u doit tre un diviseur de qv et de r. Comme un diviseur de v est un diviseur de qv, un diviseur de u et v doit tre une diviseur de v et r. Algorithme dEuclide: soit u et v deux entiers. But: calculer pgcd(u, v) Si u ( v alors Si u est divisible par v (reste(u, v) = 0) alors rsultat = v Sinon rsultat = pgcd(v, reste(u, v)) Sinon rsultat = pgcd(v, u). Calculons le pgcd de 120 et 462: u = 120 et v = 462 u < v donc rsultat = pgcd(462, 120) u > v et reste(462, 120) = 102 donc rsultat = pgcd(120, 102) u > v et reste(120, 102) = 18 donc rsultat = pgcd(102, 18) u > v et reste(102, 18) = 12 donc rsultat = pgcd(18, 12) u > v et reste(18, 12) = 6 donc rsultat = pgcd(12, 6) u > v et reste(12, 6) = 0 donc rsultat = 6 ( On peut aussi concevoir des algorithmes sur des mots. Exercice: Codes de Csar Considrons le vocabulaire V = {A, B, C, Z} et les fonctions de codage: hi: V ( V avec 0 ( i ( 25 associant chaque lment de V, llment de V situ i positions plus loin dans le vocabulaire. La fin de V est continu cycliquement par le dbut. Par exemple: h2(A) = C, h7(Y) = F, h25(Z) = Z. La table ci-dessous (appele table de Vigenre) donne la dfinition de hi pour son ime rang: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z0A B C D E F G H I J K L M N O P Q R S T U V W X Y Z1B C D E F G H I J K L M N O P Q R S T U V W X Y Z A2C D E F G H I J K L M N O P Q R S T U V W X Y Z A B3D E F G H I J K L M N O P Q R S T U V W X Y Z A B C4E F G H I J K L M N O P Q R S T U V W X Y Z A B C D5F G H I J K L M N O P Q R S T U V W X Y Z A B C D E6G H I J K L M N O P Q R S T U V W X Y Z A B C D E F7H I J K L M N O P Q R S T U V W X Y Z A B C D E F G8I J K L M N O P Q R S T U V W X Y Z A B C D E F G H9J K L M N O P Q R S T U V W X Y Z A B C D E F G H I10K L M N O P Q R S T U V W X Y Z A B C D E F G H I J11L M N O P Q R S T U V W X Y Z A B C D E F G H I J K12M N O P Q R S T U V W X Y Z A B C D E F G H I J K L13N O P Q R S T U V W X Y Z A B C D E F G H I J K L M14O P Q R S T U V W X Y Z A B C D E F G H I J K L M N15P Q R S T U V W X Y Z A B C D E F G H I J K L M N O16Q R S T U V W X Y Z A B C D E F G H I J K L M N O P17R S T U V W X Y Z A B C D E F G H I J K L M N O P Q18S T U V W X Y Z A B C D E F G H I J K L M N O P Q R19T U V W X Y Z A B C D E F G H I J K L M N O P Q R S20U V W X Y Z A B C D E F G H I J K L M N O P Q R S T21V W X Y Z A B C D E F G H I J K L M N O P Q R S T U22W X Y Z A B C D E F G H I J K L M N O P Q R S T U V23X Y Z A B C D E F G H I J K L M N O P Q R S T U V W24Y Z A B C D E F G H I J K L M N O P Q R S T U V W X25Z A B C D E F G H I J K L M N O P Q R S T U V W X Y On considre lextension de hi sur V*: Hi: V* ( V* avec 0 ( i ( 25 Par exemple: Hi(ABC) = CDE Algorithme de codage dun mot selon le code de Csar : soit w ( V* et i un entier. Par ailleurs, on considre que tableV contient la table ci-dessus. But: calculer Hi(w) Si longueur(w) > 0 alors Soit c = premier(w) Rsultat = tableV [rang(c), i] . Hi(sauf-premier(w)) Sinon rsultat = ( La fonction premier(w) retourne le premier caractre du mot w. Par exemple: premier(abc) = a La fonction sauf-premier(w) retourne le mot w priv du premier caractre. Par exemple: sauf-premier(abc) = bc TableV[i, j] retourne llment de la table se trouvant la ime colonne et la jime ligne. Par exemple: TableV[3, 4] = F La fonction rang(c) retourne la position du caractre c dans le mot ABCDEFGHIJKLMNOPQRSTUVWXYZ. Il sagit donc de la position de ce caractre dans lalphabet. Par exemple: rang(E) = 5 ( On peut aussi concevoir des algorithmes travaillant la fois sur des nombres et sur des mots. Exercice: Passage dun entier cod en base dcimale un codage en base binaire. Soit n lentier coder. Lide est de diviser successivement n par 2. chaque tour, on concatne le reste (0 ou 1) gauche de la forme code courante. On sarrte quand n vaut 0. Soit n = 57. 57 / 2 = 28 reste 1 donc rsultat = 1 28 / 2 = 14 reste 0 donc rsultat = 0 . 1 = 01 14 / 2 = 7 reste 0 donc rsultat = 0 . 01 = 001 7 / 2 = 3 reste 1 donc rsultat = 1 . 001 = 1001 3 / 2 = 1 reste 1 donc rsultat = 1 . 1001 = 11001 1 / 2 = 0 reste 1 donc rsultat = 1 . 11001 = 111001 n = 0 donc la forme binaire de 57 est 111001. Algorithme de conversion dun entier en base dcimale une forme en base binaire: soit n un entier. But: calculer codage10vers2(n) Si n > 0 alors Soit r = reste (n, 2) Soit q = quotient (n, 2) Si r = 1 alors rsultat = codage10vers2(q) . 1 Sinon (r = 0) rsultat = codage10vers2(q) . 0 Sinon rsultat = ( ( Un algorithme doit tre constitu dun nombre fini doprations. Ceci ne signifie pas que lalgorithme se termine ncessairement. Exemple: numration de tous les nombres premiers. Il est clair qutant donn quil y a une infinit de nombres premiers, un algorithme rsolvant ce problme ne se terminera jamais. Selon le problme pos, un algorithme peut ou non se terminer. Exemple: savoir sil existe trois dcimales conscutives de  dont la somme vaut un n entier fix. 2. Oprations sur les mots 2.1. Prfixe Un mot w1 est prfixe d un mot w2, s il existe un mot w3 tel que w1.w3 = w2. Un mot est toujours son propre prfixe (dans ce cas w3 = (). ( est prfixe de tout mot ((.w2 = w2). 2.2. Suffixe Un mot w1 est suffixe dun mot w2, sil existe un mot w3 tel que w3.w1 = w2. Un mot est toujours son propre suffixe (dans ce cas w3 = (). ( est suffixe de tout mot (w2.( = w2). 2.3. Infixe Un mot w1 est infixe dun mot w2, sil existe deux mots w3 et w4 tels que w3.w1.w4 = w2. Un mot est toujours son propre infixe (dans ce cas w3 = w4 = (). ( est infixe de tout mot (w3. (.w4 = w2). ( Par exemple: Pour le mot abbba, nous avons: PrfixesInfixesSuffixes(((aaaabbbaabbabbbaabbbbbbbbaabbbabaabbbaabbbbbbbaabbbbbbaabbba( 2.4. Image miroir Limage miroir w~ dun mot w est la lecture de droite gauche du mot w. ( (abc)~ = cba (~ = ( a~(bc)~ = acb ( On a toujours: w~~ = w Exercice: Dfinissez loprateur ~ par rcurrence.  Rponse: ( Un mot w est un palindrome si w~= w. ( (aba)~ = aba (abccba)~ = abccba ( Exercice: Soit V = {a, b}. Soit L le langage tels que w ( L puisse tre dcompos comme w = u . u~ avec u ( V*. Que peut-on dire sur L? et sur L? Soit L = {w | w = u . x . u~ avec x ( {a, b} et u ( V*}. Que reprsente L? Que peut-on dire sur lintersection entre L et L? Que se passe-t-il si x ( {(, a, b}? ( 3. Oprations sur les langages Nous rappelons ici que lopration de concatnation est associative. Llment neutre pour la concatnation est (. ( On a donc: (ab . (ac . bd)) = ((ab . ac) . bd) = abacbd et u . ( = ( . u = u ( 3.1. Oprations ensemblistes Un langage est une partie de V*, il sagit dun ensemble de mots. Les oprations suivantes sont donc dfinies: Union Intersection Complmentation On gardera lesprit que L ( V* et que: L ( V* = L L ( V* = V* L ( ( = ( L ( ( = L On notera (L le complmentaire de L: (L = V* - L On se rappellera que: ((L = L L ( L = L ( L = ( L ( L = L ( L = V* Dautre part, nous avons: L1 ( L2 `" (L1 ( L2) Mais, nous avons: L1 ( L2 = (L1 ( L2) L1 ( L2 = (L1 ( L2)  Remarquons que l intersection peut tre exprime l aide de l union et du complmentaire: L1 ( L2 = (L1 ( L2) 3.2. Concatnation On peut tendre l opration de concatnation aux ensembles en gnral et donc aux langages en particulier. Si L1 et L2 ( V* et a ( V alors: a . L1 = {a . w | w ( V} L1 . L2 = { w1 . w2 | w1 ( L1, w2 ( L2 } Exercice: Soit L le langage sur V = {a, b} dont les mots contiennent un nombre pair de a. 1) Que peut-on dire sur a . L? Sur L . a? 2) Que peut-on dire sur L? Sur L2? Sur (L2)? Et sur (L)2? 3) Avons nous (L2) = (L)2? Rponses: Tout dabord, jouons un peu avec L. On peut commencer numrer les mots de L par taille croissante (et par nombre de a dcroissant). On a donc L = {(, b, aa, bb, baa, aba, aab, bbb, aaaa, aaaab, aaaba, aabaa, abaaa, baaaa, bbaa, baba, baab, abab, aabb, }. On remarquera que toutes les tailles de mots sont reprsentes (on peut construire des mots de toutes les tailles avec uniquement des b) 1) (a . L) contient tous les mots de L o un a a t concatn gauche. Le nombre de a est donc impair. Il sagit donc des mots ayant un nombre impair de a et commenant par a. Idem pour (L . a), si ce nest que les mots contiennent un nombre impair de a se terminent par a. 2) L est le langage dont les mots contiennent un nombre impair de a. L = {a, ab, ba, aaa , abb, bab, bba, aaab, aaba, abaa, baaa, }. Comme prcdemment toutes les tailles de mot (sauf 0) sont reprsentes. L2 est lensemble des mots w1w2 ou w1, w2 ( L. Clairement, le nombre de a des mots de L2 est pair (laddition de deux nombres pairs donne un nombre pair). Donc L2 ( L. Si on essaye dnumrer les mots de L2, on peut, pour chaque mot de L1, concatner lensemble L: L2 = (( . L) ( (b . L) ( (aa , L) ( (bb . L) ( (baa . L) ( (aba . L) ( (aab . L) ( On remarque alors que le premier terme (( . L) = L. Donc, a: L2 = L ( (b . L) ( (aa , L) ( (bb . L) ( (baa . L) ( (aba . L) ( (aab . L) ( Donc L ( L2. Si L2 ( L et L ( L2 alors L = L2 Par suite (L2) = (L) = L 3) Nous avons: (L2)= L et (L)2= (L) . (L) La concatnation de deux mots dont le nombre de a est impair forme un mot dont le nombre de a est pair (mais non nul). Un tel ensemble est clairement L priv du mot vide. Donc: (L)2= (L) . (L) = L - ( A-t-on L - ( = L? Clairement aa ( L - (, mais aa ( L. Donc (L2) ( (L)2 ( On remarquera que, dans le cas gnral, on ne peut rien dire sur: (L2) = (L)(L)? Exercice: Vrifier lassertion ci-dessus. Cherchons un langage simple qui ne vrifie pas la proprit. Choisissons L = {a}. Alors L = V* - {a}. Donc L2 = {aa}. Donc (L2) = V* - {aa}. Or L = V* - {a}, donc (L)(L) = (V* - {a})(V* - {a}) Or aa ( (V* - {a})(V* - {a}). En effet: aa = (.aa On a trouve un mot qui appartient (L2) et pas (L)(L) Donc dans ce cas (L2) `" (L)(L). Cherchons un langage qui vrifie la proprit. Choisissons L = (. Alors L = V* Donc L2 = ( . ( = (. Donc (L2) = V* Or L = V*, donc (L)(L) = V* . V* = V* Donc dans ce cas (L2) = (L)(L). ( 3.3. Opration puissance Soit U un ensemble quelconque, nous avons par dfinition: U0 = {(} Un = U . Un-1 = Un-1 . U Donc en particulier sur un langage L, nous avons: L0 = {(} Ln = L . Ln-1 = Ln-1 . L Ainsi pour un langage L nous avons: L3 = L . L . L = LLL. Si L est le langage sur V = {a, b} dont les mots contiennent un nombre impair de a, alors L2 = LL ne contient que des mots ayant un nombre pair de a. Donc en particulier sur un mot w, nous avons: w0 = ( wn = w . wn-1 = wn-1 . w ( Ainsi: w3 = www (abc)4 = abcabcabcabc ( 3.4. Opration * (toile de Kleene) Par dfinition, pour tout ensemble U: Cette dfinition est donc valable pour tout langage L. En particulier sur un vocabulaire V, nous avons: V0 = ( V1 = V . {(} = V = mots de longueur 1 V2 = V . V = mots de longueur 2 Vn = V . Vn-1 = V n-1 . V = mots de longueur n V* est lensemble des mots de toutes les longueurs possibles, cest donc lensemble de tous les mots possibles. 4. Expressions rgulires 4.1. Dfinition en intention et dfinition en extension Pour dfinir un langage, il est ncessaire de disposer dun moyen de description des mots de ce langage. La premire mthode consiste numrer les mots de ce langage. Cest ce quon appelle une dfinition en extension. Cette mthode est trs lourde et ne permet pas de dfinir des ensembles infinis. On peut aussi dfinir un langage par la description des proprits (ou du comportement) que doivent avoir les mots de ce langage. Cest ce quon appelle une dfinition en intention. Il est possible de dcrire certains types de proprits laide dun autre langage. Ce mtalangage est dabord dcrit puis une interprtation des mots de ce mtalangage sera donne. 4.2. Dfinition rcursive Soit V un vocabulaire dans lequel les symboles de M = {+, ., *, (, ), (, (} napparaissent pas. Une expression rgulire sur V sera dfinie comme un mot sur V = V ( M. Ces mots sont dfinis rcursivement de la faon suivante: ( est une expression rgulire et reprsente le langage vide; ( est une expression rgulire et reprsente le langage contenant le mot vide; w ( V* est une expression rgulire et reprsente le langage {w} si A et B sont deux expressions rgulires reprsentant les langage LA et LB alors (A + B) est une expressions rgulire reprsentant le langage LA ( LB. si A et B sont deux expressions rgulires reprsentant les langages LA et LB alors (A . B) est une expression rgulire reprsentant le langage LA . LB. A* est une expression rgulire reprsentant le langage LA avec: Lorsquil ny a pas dambigut, les parenthses ou les points peuvent tre supprims. Un langage qui peut tre dcrit par une expression rgulire est appel langage rgulier. On remarquera que tous les langages possibles ne sont pas rguliers. Exercices: Essayez de trouver quelques langages qui nont pas lair rguliers. Rponse: L sur V = {a, b} o il y a le mme nombre de a que de b. La dmonstration (un peu complique) consiste montrer quil faudrait une union infinie dexpressions rgulires pour dcrire L. ( Exercices: Trouver une classe de langages incluse dans celle des langages rguliers. Rponse: La classe des langages finis (cest--dire ayant un nombre fini de mots) est incluse dans celle des langages rguliers. ( 4.3. Exemples Les nombres entiers sont reprsents par les mots du langage dfinis par lexpression rgulire: 0 + (1+2+3+4+5+6+7+8+9).(1+2+3+4+5+6+7+8+9)* Une extension des expressions rgulires est parfois dfinie avec une dfinition de plage de caractres (entre crochets). Par exemple: 0 + [1-9].[0-9]* Le langage compos alternativement de a et de b peut tre dcrit par lexpression rgulire: (ab)* Le langage compos alternativement dun a et dun nombre quelconque de b peut tre dcrit par lexpression rgulire: a(b)* = ab* En gnral, on prfrera rserver lutilisation du symbole + pour lunion. On crira donc plutt aa* (ou a*a) que a+. aa* = a*a correspond au langage dont les mots ne sont composs que de a. (a*b*)* = (a + b)* = V* si V = {a, b} Exercice: dmontrer lgalit prcdente Rponse: Clairement nous avons (1) a*b* ( a + b. En effet, avec lexpression rgulire a*b* on dcrit (entre autres) les mots a et b. De (1), on dduit (2) (a*b*)* ( (a + b)* Or (a + b)* = V* est lensemble de tous les mots possibles, donc il ne peut pas exister de mots non inclus dans V*, donc (a*b*)* = (a + b)* ( Exercice: dmontrer que L1 ( L2 ( L1* ( L2* lments de rponse: La dmonstration peut se faire en plusieurs tapes. (1) Dmontrer que si L1 ( L2 et L3 ( L4 alors L1 . L3 ( L2 . L4 (2) Dduire par rcurrence de ce qui prcde que si L1 ( L2 alors (L1)n ( (L2)n (3) Dduire de ce qui prcde en identifiant terme terme que si L1 ( L2 alors ( (L1)0 + (L1)1 + (L1)2 + (L1)3 + ) ( ( (L2)0 + (L2)1 + (L2)2 + (L2)3 + ) (4) Conclure que si L1 ( L2 alors L1* ( L2* ( Exercice: avons nous L1 ( L2 ( L1* ( L2* ? Rponse: On peut exhiber un contre-exemple, par exemple a* ( (* ( a ( ( ce qui est clairement faux. Donc dans le cas gnral, nous navons pas L1 ( L2 ( L1* ( L2* Est-ce pour autant toujours faux? Non, car on peut exhiber un exemple: a* ( (a*)* ( a ( a* ce qui est clairement vrai. ( 4.4. Lois algbriques sur les expressions rgulires (( + R) ( (R + () ( R lment neutre de lunion (( . R) ( (R . () ( R lment neutre de la concatnation (( . R) ( (R . () ( ( lment absorbant de la concatnation R + S ( S + R R + (S + T) ( (R + S) + T R . ( S . T) ( (R . S) . T R . (S + T) ( (R . S) + (R . T) ( S + T) . R ( (S. R) + (T . R) R + R ( R (* ( ( R . R* ( R* . R ( R+ R . R* + ( ( R* Exercice: Justification de 7 Rponse: Par la mthode de la double inclusion. Soit x ( L(R.(S+T)) ( x est de la forme: x = ry avec x ( L(R) et y ( L(S+T). y ( L(S+T) ( soit y ( L(S), soit y ( L(T), soit y ( L(S) et y ( L(T) y ( L(S) ( x = ry ( L(RS) ( x ( L(RS+RT) y ( L(T) ( x = ry ( L(RT) ( x ( L(RS+RT) Donc x ( L(R.(S+T)) ( x ( L(RS+RT)) et L(R.(S+T)) ( L(RS+RT)) Rciproque x ( L(RS+RT)) ( soit x ( L(RS), soit x ( L(RT), soit x ( L(RS) et x ( L(RT) x ( L(RS) ( x = ry et r ( L(R) et y ( L(S) ( y ( L(S+T) ( x = ry ( L(R.(S+T)) x ( L(RT) ( x = ry et r ( L(R) et y ( L(T) ( y ( L(S+T) ( x = ry ( L(R.(S+T)) Donc x ( L(RS+RT)) ( x ( L(R.(S+T)) et L(RS+RT)) ( L(R.(S+T)) (L(R.(S+T)) ( L(RS+RT)) et L(RS+RT)) ( L(R.(S+T)) ) ( L(RS+RT)) = L(R.(S+T)) ( Exercice: Dmontrer que a* = ( + aa* Rponse: a* = a0 + a1 + a2 + a3 + a4 + = ( + a1 + a2 + a3 + a4 + = ( + a(a0 + a1 + a2 + a3 + a4 + ) = ( + a(a*) = ( + aa* Cette dmonstration est valable pour toutes expressions rgulires (point 12): R* = ( + RR* On remarquera que lon peut aussi bien factoriser a droite ce qui donne: a* = a0 + a1 + a2 + a3 + a4 + = ( + a1 + a2 + a3 + a4 + = ( + (a0 + a1 + a2 + a3 + a4 + )a = ( + (a*)a = ( + a*a On en dduit que aa* = a*a Dune faon gnrale R* = ( + RR* = ( + R*R ( Exercice: Justification de (* ( ( Rponse: (* = (0 + (1 + (2 + (3 + ( + ( + (2 + (3 + Dmontrons par rcurrence que (n = ( pour n>0. Cas de base: (1 = ( Rcurrence: Supposons (n = ( vraie. Nous avons (n+1 = (n . ( = ( . ( = (. cqfd Donc (* = ( + ( + ( + ( + = ( + ( = ( ( 4.5. Quelques proprits intressantes Dans ce qui suit X et Y sont des expressions rgulires. X(YX)* = (XY)*X Dmonstration: faire en exercice ( (XY)* = ( + X(YX)*Y Dmonstration: faire en exercice ( (X+Y)* = X*(YX*)* Dmonstrationpar double inclusion a) (X+Y)* ( X*(YX*)* Soit w ( (X+Y)* Donc ( n ( 0 et z1 zn ( (X+Y) tq w = z1..zn Or zi = xy tq xi ( X* et y ( Y. Donc w = x0 . y1 . x1 . . yn . xn avec xi ( X* et yi ( Y Donc w ( X*(YX*)* Donc (X+Y)* ( X*(YX*)* b) Rciproque (X+Y)* ( X*(YX*)* faire en exercice ( (X+Y)* = (X*Y)*X* Dmonstration: (X+Y)* = X*(YX*)* et x(yx)* = (xy)*x donc si x = X* et y = Y nous avons X*(YX*)* = (X*Y)*X* = (X+Y)* ( X* = (( + X + + Xn-1)(Xn)* pour n > 1 Dmonstration: faire en exercice ( (a*)* = a* Dmonstration: par double inclusion 1) Dmontrons (a*)* ( a* (a*)* = a*0 + a*1 + a*2 + a*3 + a*4 + = ( + a* + a*2 + a*3 + a*4 + ( a* 2) (a*)* ( a* Dmontrons par rcurrence que (( + a1 + a2 + ) ( (( + a1 + a2 + )n pour n>0 Pour n=1, la proprit est vraie (( + a1 + a2 + ) ( (( + a1 + a2 + )1 Supposons, le proprit vraie pour n, lest-elle pour n+1? (( + a1 + a2 + ) ( (( + a1 + a2 + )n.(( + a1 + a2 + ) est vrai car L1 ( L3 et L2 ( L4 alors L1L2 ( L3L4 or ici L1 = (( + a1 + a2 + ) ( L3 = (( + a1 + a2 + )n L2 = ( ( L4 = (( + a1 + a2 + ) Donc nous avons (( + a1 + a2 + ) ( (( + a1 + a2 + )n+1 pour n>0 cqfd (a*)* = (a0 + a1 + a2 + )* = (( + a1 + a2 + )0 + (( + a1 + a2 + )1 + (( + a1 + a2 + )2 + = ( + a1 + a2 + ( 4.6. Dfinition arborescente Une arborescence est un graphe orient, o chaque point diffrent du point nomm racine a un et un seul antcdent. La racine na aucun antcdent. Un point est en gnral appel nud.  La structure syntaxique dune expression rgulire sur V est une arborescence dfinie par rcurrence de la faon suivante: Cas de base: Si lexpression rgulire est dfinie soit par un caractre x (x ( V), soit par les symboles ( ou (, alors lexpression constitue la structure syntaxique. x ( ( Rcurrence: Si lexpression rgulire est un oprateur (unaire) portant sur une expression rgulire A ou un oprateur (binaire) portant sur deux expressions rgulires A et B. Soit respectivement: A* A . B A + B Alors, les structures syntaxiques de lexpression rgulire sont respectivement:  ( Par exemple, lexpression rgulire (0+1)*.11(1+01)*.((+0) a pour structure syntaxique:  En prenant comme prcdence des oprateurs: (((0 + 1)*) . (1.1.(((1 + (0.1))*) . (( + 0)))) ( Nous appellerons occurrences doprateurs le nombre doprateurs prsents dans la structure syntaxique. Nous appellerons occurrences datomes, le nombre dlments de V ( {(, (} prsents dans la structure syntaxique. Nous appellerons occurrences de symboles la somme des occurrences doprateurs et doccurrence datomes. ( Dans lexpression rgulire prcdente, il y a 10 occurrences doprateurs et 9 occurrences datomes. ( On remarquera que les atomes sont les feuilles (nuds terminaux) de la structure arborescente et que les oprateurs sont les autres nuds. 5. Conclusion Ce chapitre a introduit les notions fondamentales de base que sont les mots, les vocabulaires, les langages. Nous avons illustr comment tout traitement informatique est prcd par une phase de codage et se termine par une phase de dcodage. Ces deux phases constituent un traitement sur des langages. Un algorithme est une suite finie dinstructions permettant deffectuer un traitement. Parmi, les traitements envisags on aura bien sur les phases de codage et dcodage. Les langages sont des ensembles (potentiellement infinis) de mots et ce titre acceptent les oprations ensemblistes. La description densemble de cardinalit infini ne peut se faire quen intention. Les expressions rgulires constituent un formalisme intressant pour dcrire en intention la classe des langages rguliers. Nous avons introduit certains des proprits et des oprateurs associs aux expressions rgulires. Exercices Soit le vocabulaire V = {a, b, c}. numrer quelques mots de V*. quoi correspond V*? Soit L1, le langage sur V = {a, b, c} compos dun nombre pair de a. Donner des mots de L1. Soit L2, le langage sur V = {a, b, c} compos dun nombre impair de a. Donner des mots de L2. Que peut-on dire de L1 ( L2? Et de L1 ( L2? Quid de V* ( L1? Soit V = {0, 1}. Soit L lensemble des mots sur V et ne commenant pas par 0. Donnez des exemples de mots de L. quoi correspond L? Soit L = L ( {0}. quoi correspond L? Soit les rgles de codage suivantes de V1* sur V2* : a ( 0, b ( 11 Sagit-il dun codage dcodable? Pourquoi? Mme question pour les rgles a ( 0, b ( 01 Mme question que prcdemment pour a ( 0, b ( 1, c ( 01. Que ce passe-il si le codage sapplique sur L2 qui est (V* - L1) ou L1 est le langage dont les mots contiennent au moins une fois ab? Soit V = {a, b, r, c, d}. Soit L lensemble des mots suivants: {abra, brac, acad, adab, dabra}. Trouver un mot le plus court possible sur V* contenant les mots de L. Solution immdiate mais non minimale: abracadabra (l = 11) Solution minimale: ( {brac,acad, adab, dabra} ( {acad, adab, dabrac} ( {acad, adabrac} ( {acadabrac} ( acadabrac (l = 9). Trouver un algorithme qui pour un ensemble fini L de mots sur V*, calcule le mot le plus court possible sur V* contenant tous les mots de L. (cet exercice est TRES difficile). L est le langage sur V = {a, b} dont les mots contiennent au moins une fois ab. Que peut-on dire sur L? L est le langage sur V = {a, b} dont les mots contiennent une fois ab. Que peut-on dire sur L? Soit L un langage quelconque sur V. Que peut-on dire sur les expressions suivantes: L ( L V* ( L V* ( L L ( L L ( L? Soit L le langage sur V = {a, b} ayant un nombre pair de a et quelconque de b. Que peut-on dire sur les langages suivants: a.L L.a L0 L1 L2 Ln L* (a.L)0 (a.L)1 (a.L)2 (a.L)n (a.L)* (L.a)0 (L.a)1 (L.a)2 (L.a)n (L.a)* a.L0 L1 a.L2 a.Ln a.L* Rpondez aux questions prcdentes avec les complmentaires des langages indiqus. Soit L, le langage sur {x, y} o les mots ont un nombre pair de x et quelconque de y. Donner une expression rgulire dcrivant L. Idem pour L. Soit L, le langage sur {x, y, z} o les mots ont un nombre impair de x, impair de y et pair de z. Donner une expression rgulire dcrivant L. Idem pour L. Soit L, le langage sur {x, y} o chaque occurrence de y est prcde et suivi par une occurrence de x. Donner une expression rgulire dcrivant L. Idem pour L. Montrer que tout langage fini peut tre dcrit laide dune expression rgulire. Dcrire les langages reprsents par les expressions rgulires suivantes: a. (z + y)*x b. xx* + yy* c. (xx*)(yy*) d. (x*y*)z* Montrer que si le langage L peut tre dcrit par une expression rgulire alors L= Lp o p est pair peut aussi tre dcrit par une expression rgulire. quoi correspondent: a. Lp b. Lp Produire la structure syntaxique de toutes les expressions rgulire de ce chapitre. Produire la structure syntaxique de (ab*)*ab*. Idem pour ab* (ab*)*. Les structures sont diffrentes, mais les deux expressions rgulires dcrivent le mme langage. Expliquez. En dduire des rgles de transformation darborescence applicables pour les expressions rgulires. ( ( ( ( ( (  PAGE iv  PAGE 5  PAGE 3  PAGE 16 Chapitre 1 Vocabulaires, mots, langages  PAGE 17 J. Chauch & M. Lafourcade version doctobre 1998  PAGE 26 Chapitre 1 Vocabulaires, mots, langages  PAGE 25  PAGE 26 Chapitre 2 Automates detats finis et langages rguliers  PAGE 27 f V2* V1* L1 L2 V* L1 L2  L2 L1 (L1 ( L2) (L1 ( L2) A B C E D racine B A . B A + A * . 1 0 . * + 1 . 1 . 0 ( + . 0 + * 1 0 89:;<NOlmnopz{  *+,./KLjkUmHjUmHjqUmHjUmHjwUmHjUmHj}UmHjUmH jUmHmH5 j5U>EF`anopq=q n  n  n $ !EF`anopq=q0o7z/w O % f {vL"`B:pAu4n ,0o7z/w O % f . *  n  n  n  n Lijkmn|}12356VWtuvxy  )*+-.jUmHjSUmHjUmHjYUmHjUmHj_UmHjUmHjeUmH jUmHjUmHmH=.STqrsuv   + , I J K M N ] ^ { | }     ! # $ B C ` a b d e q r j5 UmHj UmHj; UmHj UmHjA UmHj UmHjG UmHjUmHjMUmH jUmHmH=   , - I J g h ( ) G H e f  G H e f :;st +,HIZ[xy jemH5mHj UmH jUmHmHYf . *  <Jk$Tj$%&'Ŀ~yvsojgda^[\ ]_\Mz'u5oGC #  <Jk$Tj$% n  n  n ./LMij"#FGde56RS{|-.KLhiPQhijCJmHCJ jCJUj5CJU5mH jUmH jemHmHT%&'()4j/>Ss6dL'()4j/>Ss6O^`ab]^þ}xsnid_Z!R\r>MU^g "sO^_(08:<@BFHLNRTXZ^`dfjlprtvx~NP` j< j-5 jOJQJmH nHOJQJmH nHOJQJH* OJQJmH  j>6 jUCJN6O^`ab]^|NRd_`ypdL^|NRd_`y|}fgw9: C y zu[\GHXY  opqr-`atu%()-}~gh  67DKH I R S ! ! !!!2!3!W!X!Z![!n!o!!!""#"h#i#### jH* j jH* jU je6 j< j j>V|}fgw9: C y ! ! ! !!!!"""""##j$o$t$u$v$w$x$ %%g%{%&o&p&''5(6(((7))){vqlgb]Xhij/0$8'()*+05IJAB(Q" !!!!"""""##j$o$t$u$v$w$x$ %%g%{%&o&p&''5(6(((7)##########j$n$o$s$$$%%#%$%5%7%i%j%p%q%w%x%%%I&K&m&n&6(7())))))*************++&+'+8+9+N+O+W+X+n+o+++++++++++++,,!,",8,9,CJB*CJ5CJ 5B*CJH* j j>6 jUmHH* jR>S>^>_>e>f>q>r>u>v>>>> j jH* CJOJQJ6CJOJQJY888888293959i9j9l9999999:::E:F:$$$$-$$l08TF:H:|:}::::::::#;$;';[;\;_;;;;;;;<<<;<<<?<s<ü{tpib^WP               >  AB  v  yz            !"  V  XY    F:H:|:}::::::::#;$;';[;\;_;;;;;;;-$$l08T$$$$;<<<;<<<?<s<t<w<<<<<<<===S=T=W==$$-$$l08T$$s<t<w<<<<<<<===S=T=W==========3>4>5>z>>>-?ž}vokfa\WR&>?[          F  IJ  ~            &  )*  ^  ab=========3>4>5>z>>>-?B?&-$$l08T$$$$-$$l08T>>=?>?????@@@@OAmAAAEEEEEFHHII2I4IHIJINIPIXIZIIIIIIIJJ J JJJ(J)J@JAJWJXJbJcJeJfJjJkJJJJJJJJJJJJJJJJJKKKK(K)K+K,K.K/K4K5KkKmKpKrKtKuKxKyK6 jnCJH* jeH* j]-?B?\?r????@@ AAAA(B)B{B1C>CdCCCC(D]D^DDDDE#E;EVEgEþ}xsnid_ZU&&&&&&HIwxAqZ   ;  J: V   8 &,&c&y&& B?\?r????@@ AAAA(B)B{B1C>CdCCCC(D]D^D  & F;8 8  & F:8 8  & FV8 8  & F88 8&^DDDDE#E;EVEgEEEEEESFTFF G GLGMGtHHHJ JJJ&gEEEEEESFTFF G GLGMGtHHHJ JJJKKKKKKKKKKKKKKKKLLLL L LLLLLL L&L)L/L0L1L5L6L7L8LL?LCLDLELFLKLLL¿«  M&&K&nByKKKKKKKKKKKKKKKKKKKKKKKLLLLL L/L0L6L7L=L>LDLELLLMLTLUL]L^L_LtLLLLLLLLLL3M4M@MAMSM]MiMjMMMMMMMKNLNYNZNNNNNNN_O`OdOeOOOOOO j jn jU6 j< jeCJCJ j> jeH*VJKKKKKKKKKKKKKKK8$$lF $$KKLLLL L LLLLLL L&L)L/L0L1L5L6L7L8L$08@$$8$$lF 8LL?LCLDLELFLKLLLMLNLSLTLULVL\L]L $8$$lF $$LLMLNLSLTLULVL\L]L^L`LrLLLLLLLL3M5M?M@MBMCMhMiMMMMN%N&N`NtNuNNNNcOdOþ}xspkfm:;` !+-abz{} (]L^L`LrLLLLLLLL3M5M?M@MBMCMhMiMMMM8$$lF MN%N&N`NtNuNNNNcOdOOOOOEPKPYPiPjPPPPPPPPdOOOOOEPKPYPiPjPPPPPPPPPP QQ(Q=Q>QYQbQRBRpRRRRRRRRRRRnSSSLTMToTTTþ|wz{  $NO_ms .1l.OOKPLPPPPPPPPPPPPPPPPPPPPP QQQQ Q!Q&Q'Q*Q+Q4Q5Q[Q\Q]Q^QaQR RRRRRRFRHRJRLRRRTR`RbRdRfRjRlRtRvRxRzRRRRRRRRRRRRRpSrStSvSzSSSSSSSSB*H* j j j j j jUmH jQYQRBRpRRRRRRRRRRRnSSSLTMToTSQTRTWTXTYTZTcTdTtTvTTTTTTTTTTTTTTTTTTTTTTTTT*U+U6U7USUTU[U]UfUgUvUxUUUUU6V7V:V;VYY8Y9Y:Y;Y@YAYDYEYFYGYsYtYYYYYY Z Z)Z*Z.Z/Z5Z6Z>Z?Z@ZEZGZJZKZUZVZaZ j j jeH* j jH*[oTTTT U9UzUUUUV0W1WWIXJXYYYYY(Z}ZZ [[[:[;[X[TT U9UzUUUUV0W1WWIXJXYYYYY(Z}ZZ [[[:[;[X[Y[[=\Y\m\\\\\\\]],]-]j]]]]]N^^ __l____%`H`J`c```````````aaRaaabb8b9bdbfbbbc#cIcCJUaZbZmZnZyZzZZZZZZZZZZZZZZZZZZZZ[[[[[[[[['[([*[+[8[:[H[I[l[m[{[}[A\C\W\X\d\e\{\|\\\\\\\\\\\\\\\]]]]]]D^F^^^^^________ j jn j j j jH*H* je jWX[Y[[=\Y\m\\\\\\\]],]-]j]]]]]N^^ __l_________9`:`H`I`````````````````a aaa=a>aaabbbb b!b)b-b0b3b9b:bDbEbSbTbdbebfbgbcc!c"c$c%c-c.cJcKclcmcncocwczc~cc$e je jnH* jX_%`H`J`c```````aaRaaabb8b9bdbfbbbc#cIcjcIcjclccd(d`d=eeeEfffggg:hhheiiBjCjjj:k;kHkkkſ|wmhc^YTOqbc      2  s      = , jclccd(d`d=eeeEfffggg:hhheiiBjCjjj:k;kHkk & F;hhhiiii]i^i_i`ibiciiiiiiiiiij9j;jjjRlSl.m/moopp qqqqqqqqqqqqqqqqq4r5r6r7r9r;r>r?r@rArBrCrErGrNrOrSrTrUrVrXrYr]r_rrrrrrrrrrrrr j j jH* jn6 jU jH* jWkkkkRlTlUlblll.m0m1m?mmmmXninjnnnnFoRoSooppkkkRlTlUlblll.m0m1m?mmmmXninjnnnnFoRoSoopp9p:pdpnpppþ}xsnid_Z&&&&hbciab GQ-fp!p9p:pdpnpppqqqqqqr_rrrPs|s~ssssstQtRttt&pqqqqqqr_rrrPs|s~ssssstQtRtttttuu8uuuuuĿ}vlbX1  Y1  1   1  @df&&&&&K&z&&&&2&&&G&]&&&&Errrrrrrrrrrssss s sssssssssss's(s-s.s/s1s5s6s7s8s=s>s?s@sEsFsGsHsesfsgshsjslssstsvswsyszs|s}ssssssssssssssssssssssss>t?t@tAtCtEtFtHtItKt j je j jn jH*H*[KtLtNtOtttttttttuuuuuuuu9u:uBuCuKuLuNuOuvuwuuuuuuuuuuuuuuuvv7v8vUvVv[v\v`vavdvevovpvzv{vvvvvvvvvww(w)w4w5w=w>wFwGwUwVwdwewpwqwywzwwwww j je j j jn jH* jYtttuu8uuuuuuv(vMv[vfvvvvvvv2wwwwwxx  & F1 huuv(vMv[vfvvvvvvv2wwwwwxxx_xxx;y{H{I{U{V{{{{{{{{{{{{{{{{{{{{{{{{{{{{{ j j jn jeH*^]{x{y{{{{{{{ |;|P|||||||+},}<}=}a}b}d}e}y}z}}{{||||||*|+|-|/|0|I|J|K|N|O|g|h|j|l|m|||||||||||||||||||||||||||||||||b}c}m}n}}}}}}}~~~~~~~~~~%~&~*~,~0~1~=~>~G~H~V~W~[~\~H* j j$ j j jn jeH* jX|||+},}<}=}a}b}d}e}y}z}}}}}}}}}},~L~~~~~~~~~~~~zupkfa\W0BC)*,-QRfgij C"}}}}}}}}},~L~~~~~~~~~~~~3stvw\~`~a~i~k~n~q~w~x~y~z~~~~~~~~~~~~~tu}~ "#()./45=>HINOTUZ[ijހ߀AH* je jn j j jH*[~3stvw:_`n@KLiĿ~ytoje`[ b E]kl+,TUWX!:_`n@KLiÂĂABFGKLRSUVZ[_`efhimnrsÁɁʁ́́сҁցׁہ܁ &')*./349=VW[H* jH* je`[\`amnrswx}‚ƒwxՄքلڄ 4st 6PQ"# j j j< j> jf j jUmH6 jn jeH*TÂĂ'(фۄ܄ þ}xsnid_Z%&'()+,   " J !'(фۄ܄ ؆ OPHIW1ی܌݌؆ OPHIW1ی܌݌ތߌA;Ŀztqi^S%Bs  %s  %s  k lmnO |tu !"#$ ݌ތߌA;Lc7(ʖ`˙̙әؙڙۙ'%% & Fs#45͎Ύ"#)*{|EF`az{;<>?ABDENOVW]^dersyzUX^_̙͙ΙϙЙљәԙՙؙ֙ٙޙߙ5: jnH* j j j[;Lc7(ʖ`˙̙әؙڙۙܙݙɾ|qf[PECAAA???'%%*s  %s  %?s  %s  %s  %s  %Ts  %s  %8s  %)s  %s  %|s  %,s  %s  %Xs  %s  %s  ۙܙݙޙߙ "#LMNOPQ$ X $ X '$ݙޙߙ "#LMNOPQ˚̚"$%)*./2367:;>?BCEFIJMOZ[f›ěśǛțʛ˛͛ΛЛћӛԛ֛כٛڛܛݛߛ ` !"#@AGHJKLQƚǚǹ 0J:CJj0J:CJUCJ 0JCJmH0JCJj0JCJU0J5:mH 0J5:j0J5:U5:CJ 0JCJmH0JCJj0JCJUCJ0JmH0J j0JU5˚̚ !"$%)*./2367:$ X $$lǚɚʚ˚͚̚ӚԚ֚ך&'+,014578;<=>?@ABCDEFGHIJKLMORSTUWXZ[^_`acdfǰǨ jOJ QJ  jOJ QJ j/ OJ QJ U H*OJ QJ OJ QJ H* 0J:CJ 0JCJmH0JCJj0JCJUCJj0J:CJU0J:CJmHA:;>?BCEFIJMNOZ[fghijklmnopqrst$tuvwxyz{|}~$›ěśǛțʛ˛͛ΛЛћӛԛ֛כٛڛܛݛߛ$ $  je  !"#$%&'()*+$+,-./0123456789:;<=>?@ABCDEFGHHIJKLMNOPQRSTUVWXYZ[\]^_`abcdeefghijklmnopqrstuvwxyz{|}~œÜĜŜƜǜȜɜʜ˜̜͜ΜϜМќҜӜԜ՜֜ל؜ٜٜڜۜܜݜޜߜ  !"#$%&'()*+,-./00123456789:;<=>?@ABCDEFGHIJKLMMNOPQRSTUVWXYZ[\]^_`abcdefghijjklmnopqrstuvwxyz{|}~ÝĝŝƝǝȝɝʝ˝̝͝ΝϝНѝҝӝԝ՝֝ם؝ٝڝ۝ܝݝޝޝߝ  !"#$%&'()*+,-./01234556789:;<=>?@ABCDEFGHIJKLMNOPQRRSTUVWXYZ[\]^_`abcdefghijklmnoopqrstuvwxyz{|}~'$30/R . A!"#$% |,,  3 ;g{,,(d'`9 0 00/R . A!"# $% |,,  3 ;g{,,(d'`6 0 0/R . A!"#$% |,,  3 ;g{,,(d'`6 0 0/R . A!"#$% |,,  3 ;g{,,(d'`3 0/R . A!"#$% |,,  3 ;g{,,(d'`3 0/R . A!"#$% |,,  3 ;g{,,(d'` Tc0CkO䯫.G3 > Іrx}S]O`=ݘ,d+̻˼@نD!"#(^Y-ui4Qzk5OpAbPcROMBMj58f'fk[u + l3v Vk$b;_4< Ϳ):sbYB9[1!YBDx1=;6e - 2eO TX?|T01H|N '>˴#u|S8!q]%Ki}Ws rЃLs9? 89@06GV!ʓ(ІuQ*;ѳTklEQЅضZ ^EQo iBVCxmk0QJLިÀKVl÷ԈE"=Ӱ-UR)rDz1ZXD&;B#`H/i ln P"8CQp Y!h8|ǵT"n@$˨L*fcd ^(GZ3q׬>qܦMZKRԞTaXKM*Y ~dM=e(Qo T 4JM > Іtx}S]O`=݆,d+2/Pa;gX,ę q(^Y꺴dw$൚' 1^1o!ڦq}Dq.f-L|F mJ|umV e+v;z}Qv\r|}M`_mh55Gm_DGF` sf*5m,eQSH7NcG z>2x?l@T|/H jq)ͩ0ajwP"R%pز|.N g}i}&rYxIju=,T0O_o> a'1P CpJ d=`l C}'QȣT}g#"ou ,f! +v5[a;L?ƉQ <;f`1Dت!ťR숶c;j5]02JWІxS]O`= **Ҽl$j H,] s]nK?. k5[$xQSO!j9y'1?s+|gيgf29Z&^inەUH 6L +7>FI-Ɔ qh,`<L΄,A"FSd.!vA\QGdA\GhYl=i˲p'O7|9ZQ/#dɣn6T$0deF;O-p;'*0SJ/QWd댾`ȡKp`/YwUUOo?A Yb~ұW.XӨFk9ͣ2 K6u1.pJE Ӯ5Q,(bԪڦUn}Uۭp\YBKK<ǨóPE"]ӨX.Ka"փ᭫qMd/jݰ<[h,c1cRH \dTbV $JeӚcX<;81Sjh}銴QcItȏI F'?Ggmg=Ӊ9 ʷ(.KҷNѴg9zg05$:?0ï  TrMFѱYJ@P  D2@xUKOQ>-Bi12Ǻ26lİJaL33-m ;' jsg@q&ӞwL6TDtJ6>B &_l܆fmJRaMaanxcyBvR K _[CƵ͍]z@}=XsxUnPHCZ@h+NM7uRSǪvrFv;i"TEXÆWTBܹqЊrrg̙s'w"[)#@U|t^SlY|`\_~jvE/_&m/ws}qyaw\lHS]*r- nѕŎȋW5NЗQSsQ)IV9w#WXbMe$"m.ZB`t_if&8K@<]FgMdgiD?1[l=N"MyW LoͫY=R,קԛuGNC/ct[ i}[%RXxw2i5'z8=Ԝ]4'9bB06lH'JIHYZp~hgtxePǘ94K3'_haFIxJ%yzlgtf }DyK _Toc434316450}DyK _Toc434316451}DyK _Toc434316452}DyK _Toc434316453}DyK _Toc434316454}DyK _Toc434316455}DyK _Toc434316456}DyK _Toc434316457}DyK _Toc434316458}DyK _Toc434316459}DyK _Toc434316460}DyK _Toc434316461}DyK _Toc434316462}DyK _Toc434316463}DyK _Toc434316464}DyK _Toc434316465}DyK _Toc434316466}DyK _Toc434316467}DyK _Toc434316468}DyK _Toc434316469}DyK _Toc434316470}DyK _Toc434316471}DyK _Toc434316472}DyK _Toc434316473}DyK _Toc434316474}DyK _Toc434316475}DyK _Toc434316476Ddh<  C ABJNq="Kl&s d TNq="Kl>RhCxcc1 A< 2op Bi l,PQ$#4QBΩy%E 9I 7x_R+1A E}*A*.`}  h1Ao^ nEF͜ lI9@AgMϠx 559e v& nXq;# E+ [4@4NormalCJOJPJQJmH L@LTitre 1$&d@&5:CJ KHOJ QJ >@>Titre 2$h<@&5:OJ QJ F@FTitre 3$0<@&56OJ QJ 2A@2Police par dfaut.O. Heading 0$CJ(<O<Corps de texte$OJ QJ &O&Exemple("(Rappel 0,O2, Proprits,OB, Dfinition8@R8En-tte  ! 5:CJ8 @b8 Pied de page  !,)@q,Numro de page(OA(ExerciceCJDOD SubHeading 1 x:CJ OJ QJ (O(cqfd $CJ,@,TM 1 x5CJ,@,TM 2 x6CJ$@$TM 3CJ$$TM 4CJ$$TM 5CJ$$TM 6 CJ$$TM 7!CJ$$TM 8"CJ$$TM 9#CJ2B2 Exemple titre$6HoRHExercice ennonc%$7xx6Ob6Algo exo& $ ,Or,end-bloc'$CJNYNExplorateur de document(-D OJ QJ 4U@4Lien hypertexte>*B*@V@@Lien hypertexte suivi>*B*  !$(,-9EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~ )(:+3  !"#$%&'( )!*"+#,$-%.&/'0(1)2*3+4,5-6.7/8091:2;3<4=5>6?7@8A9B:C;D<E=F>G?H@IAJBKCLDMENFOGPHQIRJSKTLUMVrvx|z}NWaXhYrZs[t\u]v^w_x`yazb{c|d}e~fghijklmnopqrstuvwxyz{|}~      ! " # $ % &'()*+,-./012345678 9!:";#<$=%>&?'@(A)B*C+D,E-F.G/H0I1J2K3L4M5N6O7P8Q9R:S;T<U=V>W?X@YAZB[C\D]E^F_G`HaIbJcKdLeMfNgOhPiQjRkSlTmUnVoWpXqYrZs[t\u]v^w_x`yazb{c|d}e~fghijklmnopqrstuvwxyz{|}~      ! " # $ % &'()*+,-./0 2 34567891;<=>?@A B!C"D#E$F%G&H'I(J)K*L+M,N-O.P/Q0R1S2T3U4V5W6X7Y8Z9[:\;]<^=_>`?a@bAcBdCeDfEgFhGiHjIkJlKmLnMoNpOqPrQsRtSuTvUwVxWyXzY{Z|[}\~]^_`abcdefghijklmnopqrstuvwxyz{|}~         !$(,-9EFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~   !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~     p)5hTк @@@@@@@@ @ @ @ @ @@@@@@@@@@B@@pp))9!*22{=EHHLmUwZpbWjbqu{"<kl   ;9 ---------//GqssuCCCEEHL. `#9,8>yKOSaZ_;hrKtwy{\~A[#ǚTXYZ]`cgp| %6 !7)**n++|,,-.1z68F:;=B?^DJK8L]LMPoTX[_jckptx]{}݌ۙ:t +Heٜ0Mjޝ5RoUW\^adfhjkmoqsuwxz}f '^ )++},2-.c27F:s<-?gELLdOTIckpuy|~;ݙV[_beilnrtvy{~9;Nmoz +.Kjm|25Vux *-Sru +JM]| #Badq,Ig (Ge G e  : s + H Z x . L i  " F d 5R{-KhPh^ %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 4 !(*/69dkn6=@H!!!!!!!!!0 `B$c0CkO䯫.G32B$ 4JM޾B$dXg֧G*C@nB$~KΗ">02B$GVdB$MFѱYJ@PzxB$DIX}u xwB$V!b^kâx@0mp  !"#$%&'()*+,+-+.+/+0123456789:;<=>?@ABCDCEFGHIJKLMNOPQRSTUVWXYZ[\]^]_`abcdefgfhijklmnopoqrstuvwxyz{|}~N.(  b? 62   62     BCPDE(F P_@0`0Ht @   T  C  T  C  T  C  @  0P" 42     ! Z   3   0P" @   %! 42   !#!Z  3   %! <  # AB  3 A @ `!  9 L m5!; "m~! 4  m5 ;x  0J:!;2 42  6:'B2   6N:\x  0OZ9 ;& x  0a718 x  0 `u)  `B  c $Dg l + 0    l 3 0  @  -| k3  T $ C  -k3*B2 &   .82)H2 ' # ".2*x ( 0  A12%  x ) 0 .0+  H2 * # { ..2BT , C -| k3  6 BCDELFVt8`L 8(TXT 8l8t(,@`8u/41-N2 5 3 |./2tH2 4 # -.2< 7 # A-< > # A @  L" rB qB 6Dg 0pG~ r 6Pr@|0. PrB uB 6Dg @pL~ v 6Qv@|0* QrB w 6Dg t F~ x 6Rx |B RrB yB 6Dg  !~ z 6Tz !" TrB { 6Dg $!~ | 6S|0! "' S~ } 6U}Lp) UfB @ 6Dg "6$r  6c"7/ cfB  6Dg "5$r  6a"4/ afB @ 6Dg "3=r  6`"2; `fB  6Dg "1;r  6_"09 _r  6^"/" ^fB  6Dg ".0r  6d"-7 dfB @ 6Dg ",-r  6e"+@ efB  6Dg "*-r  6h")0 hfB @ 6Dg "(0r  6g"'0 gfB  6Dg "&0r  6f"%0 ffB @ 6Dg "$4r  6p"#7 pfB  6Dg ""4r  6o"!7 ofB @ 6Dg " ?r  6n"F nfB  6Dg "?l  0m"F mfB  6Dg "7l  0l"; lfB @ 6Dg "7l  0k"= kfB  6Dg "7l  0j"= jfB @ 6Dg ">l  0r"> rfB  6Dg ">l  0q"> q<  # A@  4!o9 6L P4o9 P4o9~  6X 4_6 X~  6W P8@o9 WHL @A6p/8 @A6p/8rB B 6Dg  @E6/8 rB  6Dg  A6p8"~  6V 8o9 VL  59  4o9x  0] 56# ]lB  0Dg 6@8x  0\ 089 \&L 4!o9 4!o9x  0[!4 _6 [x  0Z!8o9 Zx  0Y!8!o9 YJZ @A6p/8  76 %8lB B 0Dg @E6/8lB  0Dg A6p8B S  ?}jklmopqrFI)K*K+K?YEZ`{z||||||||||||||||||||||||}}}}}}}}} } } } }r}<}%4 X,tX,tt <tHth \t|t |t>p $49HpGt}tt3ot+  ot Z447@4sttRtxAht8(btX1xt@tp x0tH08th`  t@t @t"tQxtH8rthAt p t p tP  t p t  t t x tp t`ttttt0tH`t  t t x t tt(P t@ tt" _Toc432438339 _Toc432438341 _Toc432438342 _Toc432438343 _Toc434316449 _Toc432438344 _Toc434316450 _Toc432438345 _Toc434316451 _Toc434316452 _Toc434316453 _Toc434316454 _Toc434316455 _Toc434316456 _Toc434316457 _Toc434316458 _Toc434316459 _Toc434316460 _Toc434316461 _Toc434316462 _Toc434316463 _Toc434316464 _Toc434316465 _Toc434316466 _Toc434316467 _Toc434316468 _Toc434316469 _Toc434316470 _Toc434316471 _Toc434316472 _Toc434316473 _Toc434316474 _Toc434316475 _Toc434316476Fapq)4,BBCHDEGH/IK#W?YZ[] dksy"  !_m##3P,BBCSDEeHKIK;WcY[8[]dksy/>Gkq|\_be %%%%%%%%&&&%&/&7&C&M&b&m&y&&&&&&&&&&&&''' ','7'E'P'Z'b'p'{'''''''''''''(((.(:(E(S(b(n(y((((((((((())))----..:.>.h.l.v.z.....b/f/////00R0V000001 1@1D13&3K3O3 ::::::(;4;t;;;;;;;;;;;;6E;EyE{E}EEEEEEEEEEEEEEEEEEEEEEEEEEEE>FAFOFQFVFYFFFFFFFFGHHIIIINNNN!N$N&N)N+N.N0N3N5N9N;N@NBNGNINNNPNUNWN\N^NbNjNnNpNtNvNzNvPxPzP}PPPPPPPPPPPPPPPRR&R(R1R4R=R@RIRLRRRRRRRRRRRQTSTbTdTxUzUUUUUUUUUWWXX!Y$Y0Yj|1Qbxy~/~8:MBCx  ^$  f g z !k!8##$$$%%%%%%%%%%%%%%%%&&&&&&%&'&7&9&M&S&V&Z&a&b&m&u&x&y&&&&&&&&&&&&&&&&&&&'''' '"'+','7'9'P'R'b'd'{'}''''''''''''''''(((((((.(0(9(:(E(G(R(S(b(d(y({((((((((((((((() ))))* ****!*%*=*?*G*M*U*V*|*-. . .+.H.I. /S/l/n/|////////0)0;0<0`0a0000011K1L1w11112212222222V3Y33336659y9z9999-:A:C:[:^:q:t:::;;;;< <m<<<)=z=d>>>?N?\?^???@@"@j@@@@@@@RATAAA B BKBMBBBcCC!DDDDDDDmEsEtEvEwE{E}EEEEEEEEEEEEEEEEEEEEEEEEEEEEEE5FYFvFFFG"GgGGG HDHHHHHIIIILIII J JJJ!J#J,J-J6J8JiJJJJJJJJKK'K4KKKK&LGLHLVLaLrLLMSMpMNN OWOO!P#PPP$QQQR RVRRRRRRRSS0S2ScST1TFTjTlTTTTXUlUmU}U~UUUUUUV;VtQt{tttttttuu$u8uFubusutuuuuuuu v vKvPvwvvvvvvww7w9wFwGwwwwwxx^x_xxxxxxx#y%yAyCyyyy{{{{}||}=}K}p}N~~+%/!%}ӄԄ %aRV҆Ն%>?ʈ̈fk !rswx|}#&47CHɎʎҏ4>w<_(24>’ÒŒƒȒɒ˒̒ΒВҒْ֒ؒےߒml!Sihir:Cours DEUG MASS 1P (rev 12)ml!Sihir:Cours DEUG MASS 1P (rev 12)ml!Sihir:Cours DEUG MASS 1P (rev 12)ml0ulat ulat:Cours Langage:Cours Langages ch1 (d13)ml0ulat ulat:Cours Langage:Cours Langages ch1 (d13)ml0ulat ulat:Cours Langage:Cours Langages ch1 (d13)ml0ulat ulat:Cours Langage:Cours Langages ch1 (d13)mlFlafourca:www-docs:enseignements:Cours Langage:Cours Langages ch1 (d13)mlFlafourca:www-docs:enseignements:Cours Langage:Cours Langages ch1 (d13)mlFlafourca:www-docs:enseignements:Cours Langage:Cours Langages ch1 (d13)         hhOJQJo(0o(.hh.00o(..0o(...0o(.... 88o( ..... 88o( ...... `o(....... `o(........ o(.........00o(.00o(..0o(...0o(.... 88o( ..... 88o( ...... `o(....... `o(........ o(......... hhOJQJo( hhOJQJo(0o(.o(. hhOJQJo( hhOJQJo( hhOJQJo(o(.o(. OJQJo(e OJQJo(es     @WW4p ``WW pwBwCJKUV`@``8@`H`@`R`@`^`@ GTimes New Roman5Symbol3 Arial9MT ExtraO`@Devanagari MTTimesQ ThonburiCourier New3Times;Wingdings5  Monaco]Century SchoolbookGeorgia5 Geneva#qh3*F#:&+& @Nw=Tj6>0d|<ps|mlml Oh+'0`    ( 4@HPX'ososmlslsNormalfmlm3028lfMicrosoft Word 8.0d@a?c@I k@ը"@{fNw ՜.+,D՜.+,L hp  'lirmmtl=  TitreTitle 6> _PID_GUID'AN{D4F2FB80-5D26-11D2-87C6-D0416AD1D162}  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklnopqrstvwxyz{|Root Entry@ HNSLU FBlRwBPData@R@b Z'@2@U @H1Table"@ ~}{`$keneGavWordDocumentjSummaryInformation(mDocumentSummaryInformation8u CompObj  XObjectPool   lRwlRw   FDocument Microsoft WordNB6WWord.Document.8