Remerciez-le!

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

Langages formels, calculabilité et complexité Examen du 2 février 2012 Corrigé,

Langages formels, calculabilité et complexité Examen du 2 février 2012 Corrigé, version β1 Exercice 1 – 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. 1. Analyser la décidabilité/complexité de ce problème. Correction. Mettons la grammaire en forme normale de Chomsky. Construisons un graphe G dont les som- mets 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 1Le 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 2 – Calculabilité : problème de Collatz et fonctions analytiques Une séquence de Collatz générale est déﬁnie par l’affectation x := Col(x) =    a1x + b1 si x mod p = r1 . . . . . . . . . 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 différentes. On itère cette affectation jusqu’a ce que x devienne 1(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 1. 1. 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 1. Dans ce cas répondre "OUI". Donc le problème est semi-décidable. 2. Montrer que COLLATZ est indécidable 1 Correction. Étant donnée une Machine à 2 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 = 2m3nS + i −S (c’est un codage injectif). Faisons quelques observations : –l’état q1 avec m = n = 0 correspond à x = 1 –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 = 0 ssi x −i + S mod 2 ̸= 0. Pareil, n = 0 ssi x mod 3 ̸= 0. –Pour incrémenter (décrémenter m) il sufﬁt de multiplier x par 2 (resp. par 1/2) et ajouter une constante qui corrige le numéro d’instruction active. Pour n on multiplie par 3 ou 1/3. Pour traduire M en système de Collatz on représente chaque instruction de la machine à compteurs par une ou 2 lignes de système de Collatz selon la table (on omet les 3 instructions pour n qui sont similaires) : Compteurs Collatz dans qi faire m++, aller à qj x := (x −i) ∗2 + j si x mod S = i dans qi faire m–, aller à qj x := (x −i)/2 + j si x mod S = i dans qi si m=0, aller à qj sinon qk x := x −i + j si x mod S = i et x −i + S mod 2 = 1 x := x −i + k si x mod S = i et x −i + S mod 2 = 0 (les conditions sur les modulos peuvent toutes être exprimées avec mod p où p = 6S.) la séquence de x du système de Collatz ainsi obtenu correspond à la séquence des (qi, m, n) de la machine M. En particulier, M à partir de (q0, m, n) atteindra (q1, 0, 0) ssi Collatz de 2m3nS −S atteindra 1. Si COLLATZ était décidable, l’atteignabilité dans les Machines à 2 compteurs le serait aussi. Or ce dernier n’est pas décidable, on conclut que COLLATZ aussi. 3. Construire une fonction f : R →R déﬁnissable par une formule trigonométrique explicite telle que pour les x naturels f(x) = 1 si x mod p = 0 et f(x) = 0 sinon. Correction. La fonction h(x) = p−1 Y k=1 sin2(k −x)π/p pour tout x ≡k( mod p) avec k = 1..p −1 est nulle puisque son facteur sin2(k −x)π/p est nul. Pour tous les x entiers multiples de p la valeur h(x) est la même et non nulle h(x) = h(0) = p−1 Y k=1 sin2 kπ/p. Donc la fonction f(x) = h(x)/h(0) satisfait l’énoncé. 4. Construire une fonction g : R →R déﬁnissable par une formule trigonométrique explicite qui coïncide avec Col sur tous les x naturels. Correction. g(x) = p X i=0 (aix + bi)f(x) avec f déﬁnie dans le point précédent. 5. Déduire un théorème d’indécidabilité pour les itérations des fonctions trigonométriques. For- muler précisément l’énoncé et achever la preuve. Correction. Déﬁnition 1Une fonction trigo est une fonction de x qu’on peut obtenir à partir de sin aπx, cos aπx, sin aπ, cos aπ, x, a (avec a ∈Q) en n’appliquant que des opérations arithmétiques. On déﬁnit le problème TRIGO comme ceci 2 Étant donné une fonction trigo f et un entier x, est-ce qu’il il’éxiste n tel que l’itération fn(x) égale 1 ? Théorème 1Le problème TRIGO est indécidable. Effectivement, grâce au point 2 COLLATZ est indécidable, et grâce au point 4 COLLATZ se réduit à TRIGO. Donc TRIGO est aussi indécidable. Exercice 3 – Complexité : étude d’un problème On analyse le problème EVALUER-FAMILLE suivant : On a une famille C de sous-ensembles d’un ensemble A et un entier J. Est-il possible d’obtenir tous les éléments de C à partir de singletons en utilisant l’opération ∪(union) au plus J fois ? 1. Montrer que EVALUER-FAMILLE est dans la classe NP. Correction. L’algorithme non-déterministe consiste à deviner dans quel ordre on efféctue les J unions à partir des singletons, et où se trouve chaque ensemble de C dans la séquence obtenue, à faire ces unions, et à vériﬁer qu’effectivement tous les ensembles de C sont obtenus. Tous les calculs nécessaires sont polynomiaux, donc le problème est dans NP. 2. Montrer que EVALUER-FAMILLE est NP-complet. Correction. Comme indiqué, on réduira le problème TRANSVERSAL (problème NP-complet) à EVALUER- FAMILLE. Une instance de ce problème est un graphe G et un entier K. Pour faire la réduction, on construit une famille C qui contient {a0, u, v} pour chaque arête (u, v) de G, et on prend J = K+n où n est le nombre d’arêtes de G. Cette construction est clairement polynomiale, il reste à démontrer que c’est effectivement une réduction. Ca se ramène à deux lemmes : Lemme 2Si le graphe G possède un transversal de K éléments, alors on peut construire C en J unions. Preuve. Soit T ce transversal. Pour chaque w ∈T on réunit v avec a0 et on obtient {a0, w} (ça prendra K opération. Pour chaque arête (u, v) soit u soit v est dans T, supposons que c’est u. Donc l’ensemble {a0, u} est déjà construit. En faisant union avec v on obtient {a0, u, v}. Ça necessite une union par arête, et on obtient C en K + n = J opérations. □ Lemme 3Si on peut construire C en J unions, alors le graphe G possède un transversal de K éléments. Chaque ensemble {a0, u, v} est obtenu d’une de deux façons : Aréunir a0 et u, puis ajouter v (ou la symétriques); Bréunir u et v, puis ajouter a0. Preuve. Dans le cas A on ne change rien, dans le cas B on modiﬁe la construction - on réunit d’abord a0 et u, puis ajouter v (ça n’a aucune inﬂuence sur le reste de la construction puisque {u, v} qui disparaît est inutile pour les autres éléments de C). Ainsi on obtient une nouvelle construction de la famille C en J opérations utilisant seulement la méthode A. Dans cette nouvelle construction il y a n union de type {a0, u} ∪{v} (une pour chaque arête) et L −n = K opérations de type {a0} ∪{u}. En plus, cette dernière opération est faite pour un sommet de chaque arête. Soit T l’ensemble de K sommets u telle que {a0} ∪{u} est faite. Il est transversal. □ Exercice 4 – Automates et langages : mots biinﬁnis Soit A = (Q, Σ, I, ∆, F) un automate ﬁni (I, F sont deux ensembles d’états). Un calcul sur un mot bi-inﬁni u = . . . a−1a0a1 . . . est une suite bi-inﬁnie d’états (qi)i∈Z telle que : ∀i, (qi, ai, qi+1) ∈∆. Un calcul est accepteur s’il existe une inﬁnité de i ⩽0 tels que qi ∈I et une inﬁnité de i ⩾0 tels que qi ∈F. Un mot bi- inﬁni uploads/Ingenierie_Lourd/ calcula-bil-it-e.pdf