Remerciez-le!

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

y +1/1/60+ y Théorie des langages formels Examen TEST 0 1 2 3 4 5 6 7 8 9 0 1 2

y +1/1/60+ y Théorie des langages formels Examen TEST 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 ← − codez votre numéro d’étudiant ci- contre, et inscrivez votre nom et prénom ci-dessous. Nom et prénom : . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Durée : 1 heure. Tous documents et appareils électroniques interdits. Les questions faisant apparaître le symbole ♣peuvent présenter une ou plusieurs bonnes réponses. Les autres ont une unique bonne réponse. Chaque question a au moins une bonne réponse ; aucune case cochée signiﬁe que vous n’avez pas traité la question et rapporte donc zéro point. La phrase "Quelles sont les aﬃrmations justes ?" n’implique pas qu’il y a forcément plusieurs réponses ; il peut y en avoir zéro, une ou plusieurs. Certaines questions nécessitent, pour pouvoir y répondre, de réaliser un exercice, et prennent plus de temps que les questions de type connaissance pure. Gérez bien votre temps. Questions de connaissances générales Question 1 Il est possible de tester si une expression rationnelle engendre un langage vide Faux Vrai Question 2 ♣ Soient A, B et C trois ensembles. Quelles sont les égalités justes ? A −(B ∩C) = (A −B) ∩(A −C) A −(B ∪C) = (A −B) ∪(A −C) A −(B ∩C) = (A −B) ∪(A −C) A −(B ∪C) = (A −B) ∩(A −C) Aucune de ces réponses n’est correcte. Question 3 ♣ Les expressions rationnelles sont déﬁnies par le symbole vide et les singletons sur Σ auxquels on applique les opérations Union de deux langages Intersection de deux langages Fermeture de Kleene concaténation de deux langages Complément d’un langage Aucune de ces réponses n’est correcte. y y y +1/2/59+ y Question 4 Un monoïde libre est un ensemble quelconque muni d’une loi de composition interne associative et possédant un élément neutre Vrai Faux Question 5 ♣ Quelles sont les aﬃrmations justes ? Un ensemble est ﬁni s’il est équipotent à N Un ensemble est inﬁni non dénombrable s’il est équipotent à N Deux ensembles sont équipotents ssi il existe une bijection de l’un vers l’autre Un ensemble E est ﬁni s’il existe un entier n tel que E est équipotent à l’ensemble {1, 2, ..., n} Aucune de ces réponses n’est correcte. Question 6 Il est possible de tester si une expression régulière engendre un langage inﬁni Vrai Faux Question 7 ♣ Quelles sont les aﬃrmations justes ? Une application f de E1 vers E2 est une fonction telle que tout élément de E2 a un antécédent par f Une application f est injective si tout élément de E2 a au moins un antécédent Une application f de E1 vers E2 est une fonction telle que tout élément de E1 a une image par f Une application f est surjective si tout élément de E2 a au moins un antécédent Aucune de ces réponses n’est correcte. Questions exercices Question 8 ♣ Quel est le langage accepté par l’automate déterministe suivant ? 0 start 1 2 3 a b a a b b a,b mots commençant par a et ne contenant pas aa tous les mots ﬁnissant par a et contenant aa tous les mots commençant par a mots ne contenant pas trois a consécutifs Aucune de ces réponses n’est correcte. y y y +1/3/58+ y Question 9 ♣ Soit la grammaire déﬁnie par les transitions S →aS|bS|aaX, X →aX|bX|ϵ. Cette grammaire produit le langage a∗(a ∪b)∗a∗ a∗b∗aab∗a∗ (a∗∪b∗)aa(a∗∪b∗) (a ∪b)∗aa(a ∪b)∗ Aucune de ces réponses n’est correcte. Question 10 ♣ Soit l’automate à pile M = {{s, f}, {a, b}, {a}, ∆, s, {f}} avec ∆= {((s, a, e), (s, a)), ((s, b, e), (s, a)), ((s, a, e), (f, e)), ((f, a, a), (f, e)), ((f, b, a), (f, e))}. Les mots suivants sont-ils acceptés ? baaaaaa baa abb bab abb aa Aucune de ces réponses n’est correcte. Question 11 ♣ Soit la grammaire déﬁnie par les transitions S →aX, X →aX|abX|Y, Y →baY |a. Cette grammaire produit le langage a(a ∪ba)∗(ba)∗a a(a ∪ab)∗(ba)∗a a∗(ba)∗a (a ∪ab)∗(ba)∗a Aucune de ces réponses n’est correcte. Question 12 ♣ L’ensemble des mots sur Σ = {a, b} comportant deux fois plus de a que de b est un langage Non algébrique Fini Algébrique non rationnel Rationnel Inﬁni Aucune de ces réponses n’est correcte. y y y +1/4/57+ y y y uploads/s3/ liflf-examen-test.pdf