Cet ouvrage fait partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour le lire en ligne
En savoir plus

EA 2004 informatique classe prepa mp

10 pages
Version AExercice 1Soit l’alphabet B ={0,1}.1) a) Soit l’ensemble L des mots sur B contenant un nombre impair d’occurrences de 1 etl’automate A d´efini par :0 01 L’´etat i est initial. q L’´etat f est final.- -fii 1Montrer que A reconnaˆıt le langage L.b) Montrer que le langage M constitu´e des mots sur {0,1} contenant un nombre pairde 0 et un nombre impair de 1 est reconnaissable.2) On souhaite maintenant concevoir un circuit logique qui renvoie le nombre modulo 2 de 0pr´esents dans le mot pass´e en entr´ee au circuit.On pourra utiliser les portes logiques ´el´ementaires et, ou, non et xor (ou exclusif), quel’on repr´esente simplement par :ET OU XORPorte Non Porte Et Porte Ou Porte Xora) Commen¸cons par un mot de longueur 1 : u =a, avec a∈{0,1}.Construire un circuit P `a une seule entr´ee a et une sortie s qui vaut 0 si u contient0un nombre pair de 0 et 1 sinon.nb) Supposonscon¸cuuncircuitP quiprendenentr´eeunmotudelongueur2 etposs`edenune sortie s qui vaut 0 si u contient un nombre pair de 0 et 1 sinon.Construire, a` l’aide deP , un circuitP qui r´esout le mˆeme probl`eme pour un motn n+1n+1de longueur 2 en entr´ee.c) D´eterminer, lorsque n tend vers +∞, un ´equivalent du nombre de portes logiques´el´ementaires utilis´ees dans P .n3) Soit N l’ensemble des mots u sur {0,1} tels que :|u| = 2|u|0 1ou` |u| et |u| d´esignent respectivement le nombre d’occurrences de 0 et de 1 dans u.0 1Ce langage est-il reconnaissable ...
Voir plus Voir moins
Exercice 1
Version
A
Soit l’alphabetB={0,1}. 1) a) Soit l’ensembleLdes mots surBcontenant un nombre impair d’occurrences de 1 et l’automateAaipn:re´d 0 0
1L´etatiest initial. ✗✔ ✗✔ ✢ ✢ q Le´tatfest final. ✲ ✲ i f ✖✕ ✖✕ 1 Montrer queAreconnaˆıt le langageL. b) Montrer que le langageMsmuotessedru´itstonc{0,1}contenant un nombre pair de 0 et un nombre impair de 1 est reconnaissable. 2) On souhaite maintenant concevoir un circuit logique qui renvoie le nombre modulo 2 de 0 pr´esentsdanslemotpasse´enentr´eeaucircuit. Onpourrautiliserlesporteslogiques´el´ementaireset,ou,nonetxor(ou exclusif), que lonrepre´sentesimplementpar: ✎☞ ET OU XOR ✍✌ Porte Non Porte Et Porte Ou Porte Xor a)Commenc¸onsparunmotdelongueur1:u=a, aveca∈ {0,1}. Construire un circuitP0ee´rtneeuleunes`aaet une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. n b)Supposonsconc¸uuncircuitPntntqnepdreueinmouneer´ugnoledte2rueu`edeposs une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. Construire,`alaidedePn, un circuitPn+1tnuomurpome`eblroepemˆmeltuose´riuq n+1 delongueur2enentr´ee. c)De´terminer,lorsquentend vers +teslogiqubersedepornedtnumoe´uqvilaun, ´el´ementairesutilise´esdansPn. 3) SoitNl’ensemble des motsusur{0,1}tels que :
|u|= 2|u| 0 1
ou`|u|et|u|erdcoucrrneecdse0etde1danssprentneigesd´bmoneltnemevitceu. 0 1 Ce langage est-il reconnaissable ?
Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin