Exercice 1 Lare´currencesuivanterepr´esentelacomplexite´d’unprogrammere´cursifArtiustrurocsne“diviselemod`el k pourre´gner”.R´esoudrecettere´currencepourn2=.plexacomestlQuelemmargorpude´tiA? •u1= 0 •un= 2un/2+nlogn
Exercice 2 1 1. Pourchacun des quatre automates Figure 1, dire si le langage qu’il reconnait est : ⋆ ⋆+ + a.) (ab() b.)ab)ac.) (ab() d.)ab)a a b a A =B = a b a b a C =D = a
Figure 1:Les quatre automates
2.D´eterminerl’expressionre´gulie`recorrespondanta`l’automateFigure2.Donnerles´etapesducalcul. b 2 a a a b 1 3