ENIM Département Informatique

2009\2010

INFORMATIQUE THEORIQUE

ENIM Département Informatique systemesdeproduction.blogspot.com

2009\2010

EXERCICE 1On a l’ensemle G3 suivant :

1 DEVOIR LIBRE 2

systemesdeproduction.blogspot.com

Réalisé par :

systemesdeproduction.blogspot.com

DEVOIR LIBRE 2

systemesdeproduction.blogspot.com

G3=<v={a, b}, c={S,A ,B}, S, P={S→ aB, S→bA, S→v, A→aS, A→bAA, B→bS,

B→aBB} >L0(G3)= { v }L1(G3) = { v }L3(G3)= {v, ab, ba}L4(G3)= { v, ab, ba ,abab ,abba, baab, baba}...

EXERCICE 2

Debut

I :=4 ;J :=1 ;

Tant que I>1 faire

ENIM Département Informatique

2009\2010

Debut J :=J*I ; I :=I-1Fin. 1-Ce programme calcule le factoriel de I=42-On dessine l’arbre syntaxique :

2 DEVOIR LIBRE 2 2

systemesdeproduction.blogspot.com

ENIM Département Informatique

2009\2010

3 DEVOIR LIBRE 2 3

systemesdeproduction.blogspot.com

ENIM Département Informatique

2009\2010

4 DEVOIR LIBRE 2 4

systemesdeproduction.blogspot.com

EXERCICE 3   : La sémantique des expressions : S(H,U/V) , s(H,U div V), S(H,U mod V)

Soit u ,v Є V* , H Є INT

1- Si <chiffre>=>* u et <chiffre>=>* v

S (H, u) | S(H, v) si S(H, u) Є Z et S(H, v)Є Z*

S (H, u|v) = ∞ si S(H, v) =0

┴ si non

2- Si <chiffre>=>* u et <chiffre>=>* v

S (H, u) div S(H, v) si S(H, u) Є Z et S(H, v)Є Z*

S (H, u div v) =

┴ si non

3- Si <chiffre>=>* u et <chiffre>=>* v

S(H, u) mod S(H, v) si S(H, u) Є Z et S(H, v)Є Z*

S (H, u mod v)=

┴ si non

ENIM Département Informatique

2009\2010

5 DEVOIR LIBRE 2 5

systemesdeproduction.blogspot.com

Exercice 4   : Soit le programme suivant :

Debut

n := 4 ;

I :=1 ;

F :=1 ;

Tant que F < n faire

Debut

I :=I+1;

F :=F*I;

Fin tant que

Fin

L’analyse sémantique de ce probleme est la suivante :

S Prog (Prog) =Ŝ(Nil, n:=4, I :=1, F :=1, boucle)

=Ŝ (Ŝ (Nil, n:=4, I :=1, F :=1), boucle)

ENIM Département Informatique

2009\2010

6 DEVOIR LIBRE 2 6

systemesdeproduction.blogspot.com

=Ŝ (Ŝ (Ŝ (Nil, n:=4, I :=1), F :=1), boucle)

=Ŝ (Ŝ (Ŝ (Ŝ (Nil, n:=4), I :=1), F :=1), boucle)

= Ŝ (Ŝ (Ŝ ([n:=4], I :=1), F :=1), boucle)

= Ŝ (Ŝ ([n:=4, I :=1], F :=1), boucle)

= Ŝ ([n:=4, I :=1, F :=1], boucle)

Mais Ŝ ([n:=4, I :=1, F :=1], F<n) = Vrai

S Prog (Prog)= Ŝ (Ŝ ([n:=4, I :=1, F :=1],debut I:=I+1; F;=F*I, Fin), boucle)

= Ŝ (Ŝ ([n:=4, I :=1, F :=1], I:=I+1; F;=F*I), boucle)

= Ŝ (Ŝ (Ŝ ([n:=4, I :=1, F :=1], I:=I+1), F;=F*I), boucle)

= Ŝ (Ŝ ([n:=4, I :=2, F :=1], F:=F*I), boucle)

= Ŝ ([n:=4, I :=2, F :=2], boucle)

Mais Ŝ ([n:=4, I :=2, F :=2], F<n)=Vrai

S Prog (Prog)= Ŝ (Ŝ ([n:=4, I :=2, F :=2],debut I:=I+1; F;=F*I, Fin), boucle)

= Ŝ (Ŝ ([n:=4, I :=2, F :=2], I:=I+1; F;=F*I), boucle)

= Ŝ (Ŝ (Ŝ ([n:=4, I :=2, F :=2], I:=I+1), F;=F*I), boucle)

= Ŝ (Ŝ ([n:=4, I :=3, F :=2], F:=F*I), boucle)

= Ŝ ([n:=4, I :=3, F :=6], boucle)

Mais Ŝ ([n:=4, I :=3, F :=6], F<n)=faux

D’où :S Prog (Prog)= [n:=4, I :=3, F :=6]

7 DEVOIR LIBRE 2 7