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

Calculabilité - Décidabilité (LI347)oCours n 6Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚6) 1 / 20Résumé du cours précédentGrammaire hors-contexte : une façon de décrire un langage par desrègles récursives. Un grammaire consiste en des variables, dessymboles terminaux, un symbole de départ et des règles de productionDérivations et langages : le langage associé à une grammaire estl’ensemble des mots constitués de terminaux que l’on peut dériver àpartir du symbole de départDérivations droites et gauches : on remplace à chaque fois la variablela plus à gauche (à droite)Arbres de dérivation : un arbre de dérivation est un arbre qui captureles informations essentielles d’une dérivation.Ambiguité : une grammaire est dite ambigue si on peut trouver unmot de terminaux ayant deux arbres de dérivation distincts ou bien demanière équivalente deux dérivations grauche (ou droite) distinctesS. Graillat (Univ. Paris 6) LI347 (cours n˚6) 2 / 20Automates à pilesAutomates associés aux langages hors-contexte.Extension des AFN à ε-transitions auxquels on ajoute une pile.Reconnaissance des langages par états acceptantsReconnaissance des langages par pile videÉquivalences et langages hors-contexteAutomates à pile déterministesS. Graillat (Univ. Paris 6) LI347 (cours n˚6) 3 / 20Définition d’un automate à pileAutomate fini non-déterministe qu’on dote d’une pile (structure de donnéesclassique).Fonctionnement ...