Calculabilité - Décidabilité (LI347) [0.3cm] Cours no4

Calculabilité - Décidabilité (LI347)oCours n 4Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚4) 1 / 26Résumé du cours précédentEquivalence entre expressions régulières et automates finis : on peutconvertir un AFN en ER. On peut aussi convertir une ER en un ε-AFN.Loi algèbrique sur les expressions régulières : permet de simplifier desexpressionsLe lemme de pompage : permet de prouver qu’un langage n’est pasrégulierS. Graillat (Univ. Paris 6) LI347 (cours n˚4) 2 / 26Propriétés de fermetureEnoncés du type : si certains langages sont réguliers et un langage L estobtenu via certaines opérations sur ces langages réguliers, alors L estrégulier.Opérations de nature ensemblisteConcaténation, renversement, fermetureS. Graillat (Univ. Paris 6) LI347 (cours n˚4) 3 / 26Propriétés de fermeture (suite)Soit L et M deux langages réguliers. Alors les langages suivants sontréguliers :Union : L∪MIntersection : L∩MComplémentaire : LDiffèrence : L\MR RRenversement : L ={w : w ∈ L}∗Fermeture : LConcaténation : LMS. Graillat (Univ. Paris 6) LI347 (cours n˚4) 4 / 26Union, concatenation et fermetureThéorème 1Soit L et M deux langages réguliers. Alors L∪M est régulier.Preuve : Soit L= L(E) et M = L(F) avec E et F des ER. On a alorsL∪M = L(E)∪L(F) = L(E +F) par définition. Théorème 2Soit L et M deux langages réguliers. Alors LM est régulier.Preuve : Soit L= L(E) et M = L(F) avec E et F des ER. On a alorsLM = L(E) ...