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

Calculabilité - Décidabilité (LI347)oCours n 5Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 1 / 36Résumé du cours précédentPropriété de fermeture des langages réguliers : union, intersection,complémentaire, différence, fermeture, concaténation, renversementCoûts des conversions entre les représentations : AFD, AFN, ε-AFN,ERPropriété de décision des langages réguliers : tester si un langage estvide, si un mot appartient à un langage, si deux langages sont égauxMinimisation d’un automate : un automate reconnaissant le mêmelangage mais avec le moins d’états possibles (unicité de l’automateminimal)S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 2 / 36Partie II :Automates à piles, grammaireshors-contexte et langageshors-contexteS. Graillat (Univ. Paris 6) LI347 (cours n˚5) 3 / 36Grammaires et langages hors-contexteDéfinition d’un ensemble de langage contenant strictement les langagesréguliers.Notation récursive naturelle (les grammaires)Rôle central dans les années 60 pour la compilationCompilation, Parsers, XMLModèle plus puissant, Automates à pile.S. Graillat (Univ. Paris 6) LI347 (cours n˚5) 4 / 36Grammaires hors-contexte∗ RLangage défini par les palindromes L ={w ∈Σ : w = w }palPar exemple otto ∈ L , laval ∈ Lpal palPosons Σ ={0,1}Application du lemme de pompage : L n’est pas régulier!paln nSoit n donné par le lemme de pompage, regarder 0 10 .Définition récursive du langage :Base : ε, 0 ...