EA 2004 informatique classe prepa mp

Description

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 ...

Informations

• Publié par: aiolos
• Nombre de lectures: 70
• Langue: Français

Extrait

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:fire´d 0 0

1 L’´etatiest initial. ✗✔ ✗✔ ✢ ✢ q L’e´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 l’onrepre´sentesimplementpar: ✎☞ ET OU XOR ✍✌ Porte Non Porte Et Porte Ou Porte Xor a)Commenc¸onsparunmotdelongueur1:u=a, aveca∈ {0,1}. Construire un circuitP 0 ee´rtneeuleunes`aaet une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. n b)Supposonsconc¸uuncircuitP n tntqnepdreueinmouneer´ugnoledte2rueu`edeposs une sortiesqui vaut 0 siucontient un nombre pair de 0 et 1 sinon. Construire,`al’aidedeP n , un circuitP n+1 tnuomurpome`eblroepemˆmeltuose´riuq n+1 delongueur2enentr´ee. c)De´terminer,lorsquentend vers +∞teslogiqubersedepornedtnumoe´uqvilaun, ´el´ementairesutilise´esdansP n . 3) SoitNl’ensemble des motsusur{0,1}tels que :

|u|= 2|u| 0 1

ou`|u|et|u|er’dcoucrrneecdse0etde1danssprentneigesd´bmoneltnemevitceu. 0 1 Ce langage est-il reconnaissable ?