Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Calcula bil it e Langages formels calculabilité et complexité Examen du février Corrigé version ? Exercice ?? Grammaires un petit exercice On considère le problème ESTFINI suivant Étant donné une grammaire hors contexte décider si elle engendre un langage

Langages formels calculabilité et complexité Examen du février Corrigé version ? Exercice ?? Grammaires un petit exercice On considère le problème ESTFINI suivant Étant donné une grammaire hors contexte décider si elle engendre un langage ?ni Analyser la décidabilité complexité de ce problème Correction Mettons la grammaire en forme normale de Chomsky Construisons un graphe G dont les sommets sont les non-terminaux de la grammaire et il y a un arc de A à B s ? il existe une règle A ? BC ou A ? CB dans la grammaire Lemme Le langage est in ?ni si et seulement si le graphe G contient un cycle Preuve A COMPLÉTER Le parcours de graphe en largeur ou en profondeur permet de détecter un tel cycle donc le problèmes est décidable Toutes les étapes de l ? algorithme mise en forme de Chomsky construction de graphe recherche de cycle sont polynomiaux donc le problème est dans la classe P Exercice ?? Calculabilité problème de Collatz et fonctions analytiques Une séquence de Collatz générale est dé ?nie par l ? a ?ectation F F F F a x b si x mod p r x Col x F F akx bk si x mod p rk Les coef ?cients ai et bi sont des constantes rationnelles p et ri des constantes entières toutes les ri sont di ?érentes On itère cette a ?ectation jusqu ? a ce que x devienne ou jusqu ? à l ? in ?ni Si x devient non-entier on s ? arrête aussi une pathologie à éviter On analyse le problème COLLATZ suivant Étant donnés un système de Collatz général et une valeur initiale de x naturelle décider si la séquence commençant par x atteint éventuellement la valeur Montrer que COLLATZ est semi-décidable récursivement énumérable Correction Le semi-algorithme pour COLLATZ est comme ceci pour un x donné itérer la fonction jusqu ? à ce qu ? on obtienne Dans ce cas répondre OUI Donc le problème est semi-décidable Montrer que COLLATZ est indécidable CCorrection Étant donnée une Machine à compteurs de Minsky M on la simulera par Collatz en choisissant S premier et supérieur au nombre d ? instructions de M et en codant le fait que la machine se trouve dans l ? état qi avec compteurs m et n par x m nS i ?? S c ? est un codage injectif Faisons quelques observations ??l ? état q avec m n correspond à x ??pour conna? tre le numéro de l ? état o? se trouve M il suf ?t de calculer x mod S ??Dans l ? état qi on a m ssi x ?? i S mod Pareil n ssi x mod ??Pour incrémenter décrémenter m il suf ?t de multiplier x par resp par et ajouter une constante qui corrige le numéro d ? instruction active Pour n on multiplie par ou Pour traduire M en système de Collatz on représente chaque instruction de la machine à compteurs par une ou lignes