Théorie des langages : Exercices langages automates non determinisme grammaires
Télécharger PDFRICM3Langages,Automates,Non-déterminisme,Grammaires
Durée:2h00,sansdo cuments.
Touslesappareilsélectroniquessontinterditsàl'exceptiondesmontres.
Lebarèmeestdonnéàtitreindicatif.
Lesujetcomp orte4exercicesindép endants.
Nerép ondezpassurlesujet;rép ondezsurvotrecopie.
Exercice1:(7pt)Questionsdecours
Justi ezchacunedevosrép onsesdefaçonprécise(3ou4lignessu sentp ourdémontrezvotrerép onse).
Chaquequestionestnotéedelafaçonsuivante:1 4
desp ointsp ourlarép onseet3 4
desp ointsp ourla
justi cation.
1.1Éliminationdesetdéterminisme
Q1.Donnezl'automateobtenuparéliminationdestransitionsdansl'automateci-dessous// ?>=<89:;1 a **
?>=<89:;765401232 ajj b
Q2.L'automateobtenuest-ildéterministe? Q3.Unautomate niquicontientdestransitionsest-ilforcémentnon-déterministe? Q4.L'éliminationdestransitionspro duit-elleforcémentunautomatenon-déterministe? 1.2Complémentaire,pro duitetrestriction
Onconsidèrel'alphab etΣ ={a,b,c}
Q5.Qu'est-cequ'unlangagesurl'alphab etΣ?
Q6.DonnezunautomatequireconnaîtlelangageΣ
Q7.Quelestleplusgrandlangagesurl'alphab etΣ?
Q8.DonnezunautomatequireconnaîtlelangagecomplémentairedeΣ
Q9.Complétezladé nitiondeΣ+ def
=.........etdonnezunautomatequireconnaîtlelangageΣ+ Q10.DonnezunautomatequireconnaîtΣ +
Q11.Décrivezenunephraselelangagereconnuparl'automatedelaquestionprécédente.
Q12.Donnezunautomateminimalquireconnaîtcelangage.
Q13.DonnezunautomatequireconnaîtlelangageΣ∗ \Σ
Q14.Donnezunautomatequireconnaîtlecomplémentairedecelangage.
Q15.Décrivezenunephraselelangagereconnuparl'automatedelaquestionprécédente.
Q16.Quelestlelangagereconnuparlepro duitdesautomatesA1 etA2 ci-dessous.A 1def =// ?>=<89:;1 a// ?>=<89:;765401232 b ezz ?>=<89:;765401234 dOO f:: ?>=<89:;3 coo A2 def= //
GFED@ABC1 ′a
GFED@ABC4 ′d oo
GFED@ABC2 ′b //
GFED@ABC3 ′c OO
1.3Langagerégulier,langageirrégulier
Q17.Unlangage nip eut-ilêtrerégulier? Q18.SiL∩RestirrégulieretRunlangagerégulier,quep eut-ondiredeL?Donnezunepreuve.
Q19.SiLestirrégulieralorsLest....................Donnezunepreuve.
Q20.SoitA1 etA2 desautomatesàétats nis;L 1
unlangagereconnuparA1 etL2 lelangage
reconnuparA2 .Expliquezleprincip edeconstructiondel'automatequireconnaîtlelangageL1 \L2 àl'aidedesop érateurssurlesautomates.
Q21.SilelangageL\L′ estirrégulieretsiL′ estrégulieralorsLest....................Complétez
lapreuve.
Preuve:RappelonsqueL\L′ def
=.............
Puisque....est..............alors....estunlangage....................
etcommeL\L′ =...........est.................alors...est.................(d'aprèsla
question....). Q22.Lelangage{an an |n≥1}est.................Prouvez-le.
Q23.DéduiredesquestionsprécédentesquelelangageLdef ={ap |p≥1,ppremieroupair}est
irrégulier.
Preuve:L′ def={a 2n
|n≥1}est..............(d'après....). Or...........=......................quiest.................
Donc...estirrégulier(d'après....). Q24.Unlangage nip eut-ilêtreirrégulier? 1.4Grammairesetautomates
Q25.Donnezunegrammairedetyp e3(c'est-à-direrégulière)quigénèrelelangagec∗ .
Onnedemandepasdejusti cation.
Q26.Donnezunegrammairequigénèrelelangage(a+c)∗ .b
Onnedemandepasdejusti cation.
Q27.Donnezunautomateàpilequireconnaîtlelangagedespalindromesdelaformeω.c∗ .R(ω)oùω∈Σ ∗
avecΣ ={a,b}.
Onnedemandepasdejusti cation.
Q28.Cetautomateest-ildéterministe
?Justi ezvotrerép onse.
Q29.Donnezunegrammairequigénèrelemêmelangage.Onnedemandepasdejusti cation.
Q30.Donnezunegrammairequigénèrelelangagereconnuparl'automatesuivant:// ?>=<89:;765401231 a** ?>=<89:;2 a** bjj ?>=<89:;3 bjj Q31.Donnezl'expressionrégulièrecorresp ondantàl'automateprécédent.Détaillezlesétap esde
résolution.
Exercice2:(3pt)Langageirrégulier
Q32.Montrezquelelangage{0` .1k .0` |k,`∈N}estirrégulierenutilisantlelemmedugon ement.
Rapp el:Ilfautchoisirlemotωquivousfaciliteladémonstrationetilfautquecemot
dép endedelalongueurn.
Exercice3:(6pt)Preuvedecorrectionpartielledel'algorithmed'exp o-
nentiationrapide
Algorithmex:=A ;y:=N ;r:=1 ;
while(y>0){if (y%2=0){x:=x*x; y:=y/2;} else{ r:=r*x;y:=y-1; }} Q33.Donnezlestransitionsdel'automatep ourqu'ilcorresp ondeauprogrammeprécédent.
Adoptezlaprésentationci-dessousmaisrép ondezsurvotrecopie.// GFED@ABCq 0 GFED@ABC?>=<89:;q s
GFED@ABCq 111
GFED@ABCq 311 GFED@ABCq 4mm GFED@ABCq 2CC [[
Q34.Complétezl'exécutiondel'automateenadoptantlaprésentationci-dessous.Rép ondezsur
votrecopie.
a)PourlesvaleursA= 3, N= 3étatq 0
............................................
x........................
y........................
r..............................
b)Mêmequestionp ourlesvaleursA= 2, N= 0
Q35.Donnezlapropriétédecorrectionquiexprimequ'àlasortiedel'automatelavariablercontient
lavaleurdeAN .
Q36.(3pt)Preuvedecorrectionpartielle(soignezlarédaction
!)Donnezetdémontrezl'im-
plicationasso ciéeàchaquetransitionetdonnezles5invariants(ψs ,ψ1 ,ψ3 ,ψ4 ,ψ2 )asso ciésauxétatsq s,q 1,q 3,q 4,q 2. Q37.Endéduirelesconditionsd'utilisationsduprogramme.
Exercice4:(4pt)Politiquesdesécurité
Onconsidèreunréseauconstituédedeuxparties:unréseausûrcarprotégéparunpare-feuet
l'internet.
Pourcontrôlerl'usagedesmachinessurleréseauoninstallesurchaquecompteutilisateurunmoniteur
desécuritéquiobservelescommandessuivantes:
loginquilancelasessionprincipale
quitquifermelasessionprincipale
rloginquip ermetd'ouvriruneconnectionsurunemachineduréseauprotégé
sshquip ermetd'ouvrirunesessionavecencryptiondeséchangessurunemachinehorsduréseau
protégé.
exitquip ermetdefermertouteslessessionsencours(sauflasessionprincipale)
Danscetexerciceonconsidèrequelesautrescommandesquetap el'utilisateurnesontpassoumises
aucontrôledesécurité.
Princip ed'unmoniteurdesécurité:Unmoniteurdesécuritéprendenentréeunep olitiquede
sécuritéPdécritesouslaformed'uneexpressionrégulièreoud'unautomated'états niou
d'unautomateàunepiledéterministe.Ilautoriseuniquementlesséquencesdecommandes
quiappartiennentaulangageL(P).
Q38.Donnezl'alphab etΣconsidéréeparlesp olitiquedesécuritésurceréseau.
Q39.Donnez3exemplesdeséquencesdecommandesquiresp ectenttouteslescontraintesdela
p olitiquedesécuritén◦ 1ci-dessouset3exemplesdeséquencesdecommandesquinelesresp ectentpas. Politiquedesécuritén◦ 1:
1.Lasessionprincipalecommenceparunloginetsetermineparquit
2.auco eurdelasessionprincipaleonp euteectuerdessessionssshetdessessionsrlogin 3.onnep eutouvrirqu'unesessionrloginàlafoisqu'ondoitfermerparexit
4.onnep eutouvrirqu'unesessionsshàlafoisqu'ondoitfermerparexit
5.onnep eutpasavoirsimultanémentunesessionsshetunesessionrlogin
Q40.DonnezuneexpressionrégulièreP1 quidécritlap olitiquedesécuritén◦ 1.
Q41.Donnezunautomateàétats nisP2 quidécritlap olitiquedesécuritén◦ 2.
Politiquedesécuritén◦ 2:
1.Lasessionprincipalecommenceparunloginetsetermineparquit
2.auco eurdelasessionprincipaleonp euteectuersoitdessessionsssh,soitunesessionrlogin 3.onp eutouvrirauplusunesessionrloginqu'ondoitchacunefermerparexit
4.onp eutouvrirauplusdeuxsessionssshàlafoisqu'ondoitchacunefermerparexit
5.ilestinterditd'avoirsimultanémentdessessionssshetrlogin.
Q42.DonnezunautomateP3 quidécritlap olitiquedesécuritén◦ 3.
Politiquedesécuritén◦ 3:
1.Lasessionprincipalecommenceparunloginetsetermineparquit
2.auco eurdelasessionprincipaleonp euteectueruniquementsessionsssh
3.onautoriseplusieurssessionssshsimultanées.
4.onp eutouvrirautantdesessionsshqu'onveutmaisondevrafermerchacunedes
sessionsparlacommandeexit.Autrementditsionfaitssh.ssh.sshilfaudraensuite
faireexit.exit.exit.
Harmonisationdesp olitiquesdesécuritéActuellementlestroisp olitiquesdesécuritécohabitent
(certainscomptessuiventlap olitiquen◦ 1d'autreslap olitiquen◦ 2etd'autreslap olitiquen◦ 3).On
souhaiteuniformiserlesp olitiquesdesécuritéetadopterlamêmep ourtouslescomptes.Lesingé-sys
sesontréunisethésitententredeuxp olitiques:
•Lap olitiquen◦ 4quiconsisteàaccepterlescommandessiellessontautoriséesàlafoisparP 1etparP 2. •Lap olitiquen◦ 5quiconsisteàaccepterlescommandessiellessontautoriséesparP1 ouparP2 .
Consigne:Danslesquestionssuivantes,nepasconstruirelesautomates.Ondemandeseule-
mentd'expliquerlesétap esdeconstruction.
Q43.Expliquezlesétap esquip ermettentdeconstruireunedescriptionP4 delap olitiquen◦ 4,dans
undesformatd'entréedumoniteurdesécurité.
Q44.Expliquezlesétap esquip ermettentdeconstruireunedescriptionP5 delap olitiquen◦ 5,dans
undesformatd'entréeaumoniteurdesécurité.
Comparaisondep olitiquesdesécurité
Q45.Envousinspirantducours,expliquezcommentconstruireunautomatequicaractériseles
séquencesdecommandesquiappartiennentàL(P1 )∩L(P3 ).Construirecetautomate(sansdétailler
lescalculs).
Q46.Onconsidèreunep olitiquedesécuritédonnéesouslaformed'unautomated'états niPet
unep olitquedesécuritédonnéesouslaformeP′ d'unautomated'états ni
oud'unautomateàune
piledéterministe.
Donnezdespro cédésquip ermettentdecomparerlesp olitiquesdesécuritéc'est-à-direlesensembles
(L(P)etL(P′ ))deséquencesdecommandesautoriséesa np ourdéterminerlaquelledes2p olitiques
estlaplusrestrictive(resp.laplusp ermissive).ConsidérezlecasoùP′ estunautomated'états niet
lecasoùP′ estunautomateàunepile.