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

Calculabilité - Décidabilité (LI347)oCours n 8Stef GraillatUniversité Pierre et Marie Curie (Paris 6)S. Graillat (Univ. Paris 6) LI347 (cours n˚8) 1 / 32Résumé du cours précédentGrammaire et automate à pile : les langages acceptés par un AP soitpar état final soit par pile vide sont exactement les langageshors-contexteAutomate à pile déterministe : un automate à pile est déterministe s’iln’a jamais le choix de mouvement étant donné un état, un symboled’entrée et un symbole de pileLangage accepté par un APD : tous les langages réguliers sontacceptés (par état final) par un APD. Les langages acceptés par unAPD sont hors-contexte et ont une grammaire non-ambigue. Leslangages acceptés par un APD contiennent strictement les langagesréguliers et sont inclus strictement dans les langages hors-contexteÉlimination des symboles inutiles : une variable peut être éliminéed’une grammaire à moins que l’on puisse y dériver une chaine determinaux et qu’elle apparaisse aussi dans une dérivation depuis lesymbole de départS. Graillat (Univ. Paris 6) LI347 (cours n˚8) 2 / 32Résumé du cours précédent (suite)Élimination des ε-productions et des productions unitaires : étantdonnée une grammaire, on pour trouver une autre grammairereconnaissant le même langage (excepté ε) mais sans ε-production etsans production unitaire (les règles avec seulement une variable dans lecorps)Forme normale de Chomsky : étant donnée une grammaire, on peutconstruire une autre grammaire ...