Exercices autommates et grammaires Théorie des langages...

Théorie des langages : Exercices autommates et grammaires

Télécharger PDF

RICM3AutomatesetGrammaires

Durée:2h00,sansdo cuments.

Touslesappareilsélectroniquessontinterditsàl'exceptiondesmontres

Lebarèmeestdonnéàtitreindicatif

Lesujetcomp orte6exercicesindép endants

Lesujetestsur75maisilsutd'avoir50p ouravoirlanotemaximale,cequivous

donnelechoixetvousp ermetdefairel'impassesur2exercices.

Commencezparliretoutlesujetp ourrep érerlesquestionsfaciles

Exercice1:Grammairesdesidenticateurs(20min)10pt Danslaplupartdeslangagesdeprogrammationlesnomsdevariables(app elésidenticateurs)doivent

resp ecterlescontraintessuivantes:

1.lesidenticateurssontformésdelettresminuscules('a',...,'z'),delettresma juscules('A',...,'Z'),

dechires('0',...,'9'),etducaractèresouligné'- '

2.unidenticateurdoitcommencerparunelettreminusculedans'a',...,'z'

Exemple:x,ysontdesidenticateurs,A,1,- nesontpasdesidenticateurs

3.unidenticateurnedoitpasseterminerparunsouligné'- '

Exemple:x- 1,y- bsontdesidenticateurs,x- ,y- nesontpasdesidenticateurs

Q1.Donnezunegrammairedesidenticateursquiresp ectecescontraintes.

Q2.Donnezunegrammairedesidenticateursquiresp ectelescontraintesprécédentesetlescontraintes

ci-dessous(quin'existentpasdansleslangagesdeprogrammation):

4.unidenticateurnedoitpascomp orterplusieurscaractères'- 'consécutifs

Exemple:x- A- 1,y- B- 2sontdesidenticateurs,x-- ,y-- 2nesontpasdesidenticateurs

5.unchiredoitêtreprécédéducaractèresouligné'- 'oud'unchire

Exemple:x- 1,y- 2sontdesidenticateurs,x1,y2nesontpasdesidenticateurs1 Exercice2:GrammairedesdéclarationsdevariablesenC(20min)10pt LasyntaxedesdéclarationsdevariablesenCestdénieparunegrammaireavecp ourgerme,SomeDecl,

etp ourrègles:

SomeDecl→

|OneDeclSomeDecl

OneDecl→TypeVarsOptA';' Type→"int"

|"float"

V ars→OneVarMoreVars

MoreVars→

|','Vars

OneVar→grammairedel'Exercice1:OptA→ |'='Value

Value→Float|Int Q3.AttributshéritésetsynthétisésAjoutezdesattributsàlagrammaireci-dessusanquele

non-terminalSomeDeclretourneunelistededéclarationsindép endantesdesvariables,auformatdu

langagePascal,etavecleurvaleurd'initialisationsielleestprésente.

Indication:

Vousdevezpro duireunerésultatconformeauxexemplesci-dessous.

Voussupp oserezquelesnon-terminauxFloatetIntpro duisentunechaînedecaractèrescorresp ondant

àlavaleurlueetquelenon-terminalOneVarpro duitunechaînedecaractèrescorresp ondantaunom

devariablequ'ilareconnu.

Vousnevouspréo ccup erezpasdedétecterlesvariablesdéniesplusieursfois.

Exemples:

-SomeDecl[〈intx,y,z =0 ;〉] =

["x: integer= 0";"y: integer= 0";"z: integer= 0"]

-SomeDecl[〈intx =0 ;float x,y=3.14 ;〉] =

["x: integer:= 0";"x: real:= 3.14";"y: real:= 3.14"]

Exercice3:Transducteursetadditionbinaired'automates(20min)15pt Danstoutl'exerciceonconsidèredesnombresenbinaireécritsavecl'unitéàgauche.

Exemples:-(1) N≡(1) 2

≡(1.0.0.0.0)2 ≡(1.0∗ )2 -(2)N ≡(0.1)2 ≡(0.1.0∗ )2 -(3)N ≡(1.1)2 ≡(1.1.0∗ )2 Q4.DonnezunautomateAquireconnaîtlesnombresbinairesimpairs≥3,écritsaveclesunitésà

gauche.Autrementdit,{11,101,111,1001} ∈L(A)et{0,01,001}/∈L(A)

Q5.DonnezuneexpressionrégulièreéquivalenteàA2 Q6.OnconsidèreletransducteurT1 def= //

?>=<89:;76540123q 0/1II 1/0

Décrire(àchaquefoisenunephrase):

1.lelangagereconnuparletransducteurT1 2.l'eetdutransducteurT1 surlesmotsqu'ilreconnait

3.lelangagedesortiedutransducteurT1 Q7.Onconsidèrel'automateAdef =// ?>=<89:;a 1// GFED@ABC?>=<89:;a ′0 JJ1 Décrireenunephraselesnombresbinaires(avecunitéàgauche)reconnusparl'automateA.

Q8.Construisezlepro duitdeAparletransducteurT1 ,puisdécrireenunephraselelangagede

sortiedel'automateA×T1 .

Q9.DonnezuntransducteurT2 quireconnaîttouslesmotsetquiremplaceles0pardes1lorsque

le0estprécédéd'un1.

Exemples:-T 2

(001001) = 001101-T 2

(000000) = 000000-T 2

(101000) = 111100

Rapp elsurl'additionenbinaireLorsqu'onveutadditionnerdeuxnombresnetp,oncomplète

lepluscourtdesdeuxpardes0and'obtenirdesnombresdemêmetailleouonleura joutemêmeun

0p ourprévoirlecasd'uneretenueennd'addition.

Exemple:

onconsidéredesnombresbinairesécritsaveclesunitésàgauche

etdonconfaitl'additiondegaucheàdroite:

111111 =n

+ 11=p0100001 détaildescalculs:

sensducalcul

−−−−−−−−→

111111retenue

1111110 =ncomplété

+ 1100000 =pcomplété0100001 Toutnombrebinairepestéquivalentàp.0∗ :lenombrepauquelonaa joutédes0nonsignicatifs.

Q10.Construireletransducteur-additionneurTp asso ciéàl'automateAp def= //

GFED@ABCa 01 //

GFED@ABCa 11 //

GFED@ABC?>=<89:;a 20 Q11.Onsupp osequ'An etAp sontdesautomatessurΣ ={0,1}.Expliquezcommentobtenir

l'automatequireconnaitlelangage{n+p|n∈L(An ), p∈L(Ap )}.3 Exercice4:Mo délisationde proto coles

médicauxà l'aide

d'aef(30min)15pt 4.1Pro duitd'automatesharmonisés

OnconsidèrelesautomatessuivantsA 1def =// ?>=<89:;1 a// ?>=<89:;2 b// ?>=<89:;765401233 surl'alphabetΣ1 ={a, b}A 2def =// GFED@ABC1 ′a //

GFED@ABC2 ′c //

GFED@ABC?>=<89:;3 ′

surl'alphabetΣ2 ={a, c}

Q12.DécrivezlelangageL(A1 ×A2 )reconnuparl'automateA1 ×A2 .Justiezavecprécisionvotre

rép onse.

Harmonisationd'automatesLorsquedeuxautomatesn'ontpaslemêmealphab et(Σ1 etΣ2 ),on

p eutharmoniserlesautomatesdemanièreàcequ'ilsaientunalphab etcommun(Σ = Σ1 ∪Σ2 ).Cela

consisteàrendreunautomateinsensibleàunsymb olequin'étaitpasdanssonalphab et,ena joutant

àchaqueétatdel'automateuneb ouclesurlesnouveauxsymb oles.

Exemple:AΣ 1etA Σ2 ci-dessoussontlesversionsharmoniséesdesautomatesprécédentsétendusà

l'alphab etΣ ={a, b, c}A Σ1 def= //

?>=<89:;1 a// c

?>=<89:;2 b// c

?>=<89:;/.-,()*+3 cA Σ2 def= //

?>=<89:;1 ′a //b ?>=<89:;2 ′c //b ?>=<89:;765401233 ′b Q13.Constuirelepro duitAΣ 1×A Σ2 .

Q14.DonnezlelangagereconnuparAΣ 1×A Σ2 .

4.2Applicationauxproto colesmédicaux

Unproto colemédicaldécritlesactionsàeectueretl'ordredanslequelleseectuer.Souventune

op érationfaitapp elàplusieursproto colesmédicauxsimultanément.

Lebutdecetexerciceestd'étudierlesinteractionsentreplusieursproto colesandedéterminers'ils

sontcompatiblesounon.Pourcelaondécritchaqueproto coleparunautomateouuneexpression

régulière.Sonalphab etestl'ensembledesactionsduproto cole.

4.3Imageriemédicale

Proto coleP1 Oncommenceparinjecterdanslepatientunpro duitradioactif(phased'injection

=i)quip ermetdevoirunorganeparanalysedurayonnement,onp eutainsivisualiserl'organe

(phasephotographie=p).Ensuite,oninjectedespro duitsquineutraliseparcapturelespro duits

radioactifs(phaseneutralisation1,2=n1 , n2 )quisontensuiteéliminerparlecorps(phased'élimination=e). 4

Co dageduproto coleP1 sousformed'automateLeproto coleP1 p ourl'imageriemédicaleest

donnéparl'expressionrégulièresuivanteP 1def = (i.p.n1 )+ .n2 .e

Q15.Donnezl'alphab etΣ1 duproto coleP1 Q16.Donnezl'automatecorresp ondantàP1 .

4.4Interventionchirurgicale

Proto coleP2 Oncommenceparuneanalysedesang(phases)avanttouteinjection,ensuiteon

eectueunephotographiedel'organe(phasep),ensuiteonp euteectueuneséried'anesthésie(phasea)

suivied'uneinterventionchirurgicale(phasec).Ennonsurveillelepatientjusqu'àsonréveil(phaser)

Co dageduproto coleP2 sousformed'automate

Q17.Donnezl'alphab etΣ2 duproto coleP2 Q18.Donnezl'expressionrégulièrecorresp ondantàl'automateci-dessousP 2def =// /.-,()*+s //

/.-,()*+p //

/.-,()*+a r //

/.-,()*+

/.-,()*+c ]]

4.5Combinaisonsdeproto coles

Mo délisationdecontraintespardesautomatesSionsouhaitecombinerlesproto colesP1 etP 2

ilyadeuxcontraintesàresp ecter:C 1

:L'analysedesang(phases)doitavoirlieuavantl'injectiondepro duitsradioactifs(phasei)C 2

:Aprèsuneinjection(phasei),ondoitfaireuneneutralisation1(phasen1 )avanttouteanesthésie

(phasea)

Pourmo déliserlescontraintesC1 etC2 vousavezledroitd'utiliser

desexpressionsrégulières,

oudesautomates(déterministesounon)

etlesop érateursensemblistes(∩,∪,,\, ...)àconditiondejustiercommentréaliser

cetteop érationsurlesautomatesoulesexpressionsrégulières.

OnnedemandePASDECALCULmaisdedonnerunedénitionprécisedechaque

contrainteetdejustiezvotremo délisation.

Q19.Expliquezcommentmo déliserlacontrainteC1 surl'alphab etΣ = Σ1 ∪Σ2 .

Q20.Expliquezcommentmo déliserlacontrainteC2 surl'alphab etΣ = Σ1 ∪Σ2 .5 Combinaisonsdesproto colesetdescontraintes

Q21.Expliquez(précisement)commentconstruireunproto colePquiindiquecomment

pratiqueruneimageriemédicaleenresp ectantleproto coleP1 etd'eectueruneinterventionchirurgicaleensuivantleproto coleP2 toutenresp ectantlescontraintesC1 etC2 Q22.Expliquezprécisementcommentsavoirsileproto colePestréalisable? Autrementdit,donnezuncritèrequip ermetdesavoirs'ilestp ossibledesatisfairesimultanémentles

exigencesdeP1 ,P2 ,C1 etC2 .

Q23.Donnezunalgortihmequip ermetdesavoirsiPestréalisable.

Q24.(5à10lignes)ImaginonsquePsoitréalisable.Prop osezundisp ositifinformatiquequi,à

partirdel'automateP,p ermetdesavoiràchaqueétap eduproto colequellessontlesactionsautorisés.

Sivousavezrép ondusansfauteàtouteslesquestionsvousdécro cherezunjobdechefdeprojet

dansuneso ciétégrenobloisetravaillantsurlessystèmesd'informationp ourlemondemédicale

etvoussauverezdesvies.

Exercice5:Inclusionsdelangages(20min)10pt Onconsidèrel'alphab etΣ ={a, b}etleslangagesL1 àL5 ci-dessous.

Q25.Comparezleslangages2à2etindiquezlesrelationsqu'ilsvérient:⊆(inclusionlarge),⊂

(inclusionstricte),=(égalité),oubienintersectionvide.Justiezchacunesdevosrép onsesparun

raisonnementouuncontre-exemple.

Lesjusticationscomptentp our2 3

desp oints.L 1def =L( Σ∗ )L 2def =L( (b+a)∗ )L 3def =L(( (a∗ ).b+a.(b∗ )) ∗) L4 def=L (a ∗+b ∗) L5 def=L ((ab) ∗) 6

Exercice6:Constructiond'automatesreconnaisseurs(30min)15pt Onconsidèrel'alphab etΣ ={a, b}.Lebutdel'exerciceestdeconstruireunautomatequireconnaît

lelangageLformédesmotsquicontiennentaumoinsunbsiilscontiennentunnombrepairdea.

Indication:LesmotssuivantsappartiennentàL:a,b,ab,ba,bb,aaa,aab,aba,abb,baa,bab,bba,

bbb,aaab,aaba,aabb,abaa,abab,abba,abbb,baaa,baab,baba,babb,bbaa,bbab,bbba,bbbb,aaaaa,

aaaab,aaaba,aaabb,aabaa,aabab,aabba,aabbb,abaaa,abaab,ababa,ababb,abbaa,abbab,abbba,

abbbb,baaba,babaa,babab,babba,bbaaa,bbaab,bbaba,bbabb,bbbaa,bbbab,bbbba,aaaaab,...

Q26.Complétez(survotrecopie)laformulesuivantequidécritLL def={ω| (|ω| a

.............) ︸︷︷︸ Ca ......( |ω|b ..........) ︸︷︷︸C b} où|ω|s désignelenombredesymbolesdanslemotω

ConstructiondesautomatesAetBOndésigneparAl'automatequicorresp ondàlacontrainte

surlesa(accoladeCa )etparBl'automatequicorresp ondàlacontraintesurlesb(accoladeCb ).

Q27.Donnezl'automateAsurl'alphab etΣ ={a, b}.

Q28.Donnezl'automateBsurl'alphab etΣ ={a, b}.

Q29.SachantqueP⇒Qéquivautà¬P∨Q,donnezl'automatequireconnaîtlelangageLen

expliquantlesétap esdelaconstruction.

Q30.calculatoireÉliminezles-transtions.

Q31.calculatoireDéterminisezl'automate.

Q32.calculatoireMinimisezl'automate.

Q33.calculatoireDonnezuneexpressionrégulièreéquivalente.

Q34.SachantqueP⇒Qéquivautaussià¬(P∧ ¬Q),prop osezuneautremétho dedeconstruction

del'automatequireconnaîtlelangageL.

Onnedemandepasdefairelescalculs,maisuniquementdedécrirelesétap esdelaconstruc-tion. 7