Scribd
Importer
2 vues1 page

Stratégies de programmation et langages formels

Le document présente des exercices sur l'implémentation d'applications, la classification de langages et la reconnaissance de chaînes. Il aborde des comparaisons de stratégies de programmation en C et assembleur, ainsi que des questions sur les langages réguliers et non réguliers. Enfin, il demande de concevoir des automates finis déterministes (AFD) pour des langages spécifiques.

Transféré par

mmferrah
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
2 vues1 page

Stratégies de programmation et langages formels

Le document présente des exercices sur l'implémentation d'applications, la classification de langages et la reconnaissance de chaînes. Il aborde des comparaisons de stratégies de programmation en C et assembleur, ainsi que des questions sur les langages réguliers et non réguliers. Enfin, il demande de concevoir des automates finis déterministes (AFD) pour des langages spécifiques.

Transféré par

mmferrah
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

TD n° 1 COMPILATION 2 CS SQ-SL

Exercice 1 :
Lors de l’implémentation d'une application, on peut la caractériser par :
❖ Le temps de programmation, mesuré en hommes-jour (HJ), que prendra un programmeur pour la coder :
influencé essentiellement par le choix du langage de programmation.
❖ Le temps d'exécution, en millisecondes (MS), que prendra un processeur pour l’exécuter : influencé à moitié
par une partie du code que l'en implémente.
Considérons les affirmations suivantes obtenue après un benchmarking d'une application :
1) 1% du code d'une application serait responsable de 60 % de son temps d'exécution.
2) 100 HJ sont nécessaires à la programmer en C.
3) La programmation en assembleur est 10 fois plus longue (en HJ) qu'en C ; mais produit des programmes 4 fois plus
rapide.
1) Comparer les trois stratégies suivantes en de temps de programmation et de temps d’exécution :
A. Programmation de l'application entièrement en C
B. Programmation de l'application entièrement en Assembleur
C. Programmer entièrement en C, puis coder 1% (responsable de 60 % de son temps d'exécution) en Assembleur
2) Quelle est la meilleure stratégie ?

Exercice 2 :
Soit les langages définis comme suit :
• {(ab)n}, n≥0
• {anbn}, n≥0
• {anbm}, n≥0, m≥0
• {anbm}, n>m,
• {anbm}, n=m
1. Classer les langages en deux groupes réguliers et non réguliers. Justifier votre classement en vous appuyant
sur le lemme de l’étoile lorsque c’est nécessaire.

Exercice 3 :
Soit un langage L sur un alphabet ∑ = {α , β , δ, % } défini par la concaténation suivante : L = L1 . L2. L1 avec L1 et L2,
deux langages sur ∑ définis comme suit : L1 = { % } et L2 = ∑+

 Quels seraient les lexèmes de L que l'on puisse extraire (reconnaître) des chaînes suivantes ?
1) %δαβαδ% (2) δδααβ%αβαδ%αβαββ (3) %δδααβ%αβαδ%αβαββ
(4) %δαβαδ%δδααβ%αβαδ%αβαββ %δαβαδ%δδααβ%αβαδ%αβαββ

Exercice 4 :
Soit deux langages définis sur l'alphabet : 𝚺 = {0,1, a, b}
• L1 : Ensemble des chaînes avec un nombre pair de 0 et un nombre impair de 1
• L2 : Ensemble des chaînes qui ne contiennent pas la sous-chaîne 001

 Donner un AFD pour reconnaitre les mots du langage L1 et un AFD pour reconnaitre ceux de L2

Vous aimerez peut-être aussi