Fichier PDF

Partage, hébergement, conversion et archivage facile de documents au format PDF

Partager un fichier Mes fichiers Convertir un fichier Boite à outils PDF Recherche PDF Aide Contact



ETCD L2 2017 2018 THL .pdf



Nom original: ETCD_L2_2017_2018_THL.pdf
Auteur: digitec

Ce document au format PDF 1.5 a été généré par Microsoft® Office Word 2007, et a été envoyé sur fichier-pdf.fr le 23/01/2018 à 08:23, depuis l'adresse IP 105.99.x.x. La présente page de téléchargement du fichier a été vue 293 fois.
Taille du document: 728 Ko (5 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Minis ère de l’Enseignement Supérieur et de la Recherche Scientifique
UNIVERSITE ALGER 1 – Benyoucef Benkhedda
FACULTE DES SCIENCES
DEPARTEMENT INFORMATIQUE
Nature de l’examen : Contrôle (test)
Durée : 1h30mn
Date : 18/01/2018

Module : THL
Filière : L2-S3

Exercice 1 : (3 pts)
Soit la grammaire à contexte libre G = < X, V, S, P> avec
P = { S  S + S; S  S * S; S  S - S; S  S/S; S  (S); S  a }
1-Donnez les éléments constituant les ensembles X, V, S
2-Donnez un arbre de dérivation pour le mot (a + a) / ((a a) - a)
Exercice 2 : (9 pts)
Soient les langages suivants :
;

1234-

Proposer une grammaire pour chacun des langages donnés.
Complétez la définition formelle suivante (sans utiliser l’opérateur union :
Proposer une grammaire pour contenant uniquement deux non-terminaux.
Trouver deux mots de longueurs 3 que l’on peut dériver du .

Exercice 3 : (8 pts)
Soit X = {a,b}. Soit l’automate A suivant :
b

b

a
b

1

b

3

a

a

2

1. Donner le système d’équations de l’automate A
2. Déterminiser l’automate A
3. Minimiser l’automate A
4. Donner une grammaire linéaire à droite qui engendre L(A)
5. Construire l’automate complémentaire à A

Bon Courage

NB : Toute réponse non justifiée ne sera pas prise en considération

Minis ère de l’Enseignement Supérieur et de la Recherche Scientifique
UNIVERSITE ALGER 1 – Benyoucef Benkhedda
FACULTE DES SCIENCES
DEPARTEMENT MATHEMATIQUES INFORMATIQUE
Nature de l’examen : Contrôle (test)
Module : THL
Filière : L2-S3

Corrigé
Exercice 1 : (3pts)
Soit la grammaire à contexte libre G = < X, V, S, P> avec
P = { S  S + S; S  S * S; S  S - S; S  S/S; S  (S); S  a }
1-Donnez les éléments constituant les ensembles X, V, S
X= {+,*,-,/,(,),a} ; l’alphabet : ensemble des terminaux. (0.5)
V={S} ; ensemble des non terminaux. (0.5)
S : Axiome. (0.5)
2- Arbre de dérivation (Arbre syntaxique) pour le mot (a + a) / ((a a) - a)
S
S/S
(S)

(S)

S+S

S–S

a

a

(S)

(1.5)

a

S*S
a

a

Ou bien :
S S / S  (S) / S  (S+S)/S (a+a)/S (a+a)/(S) (a+a)/(S-S)  (a+a) /((S)-S)  (a+a) / ((S*S)-S) 
(a+a)/((a*a)-a)
Exercice 2: (9pts)
1- Proposons une grammaire pour les langages suivants :
« Il peut y avoir d’autres solutions pour cette question »

G1=<{a,b}, {S, A}, S, P1> avec P1= { S  a S A / A ; A  b A / b }

( 2pts)


G2 =<{a,b}, {S, A, B}, S, P2> avec P2={ SA S/ ; A  a A / a B ; B  b B /

} (2pts)


G3 =<{a,b}, {S, A, B}, S, P3> avec P3={ S A / B ; Aaa A bb / bb ; B a B b / abb } (2pts)

2- Complétez la définition formelle suivante (sans utiliser l’opérateur union :
(1pt)
3- Proposer une grammaire pour contenant uniquement deux non-terminaux :
G3 =<{a,b}, {S, A}, S, P3> avec P3={ S aa S bb / bb / A ; A  a A b / abb } (1pt)
4- Trouver deux mots de longueurs 3 que l’on peut dériver du

.

(1pt)
Exercice 3 : (8pts)
Soit l’automate A défini sur X={a, b}.
1- Le système d’équations : (1pt)

2- Déterminisons l’automate A : (1pt)
A
E0=
*{3}
E1= *{1, 2, 3}
E2= *{3,2}

---{3, 2}
{3, 2}

b
{1, 2, 3}
{1, 2, 3}
{1, 2, 3}

b

E0

b

E1
b
a

E2
3- Minimisation :
a
Pour minimiser un automate, il faut qu’il soit déterministe.
Or l’automate est déterministe, donc il reste qu’à appliquer l’algorithme de minimisation.
Pour cela, on doit séparer les états de l’automate en 2 ensembles :
- Ensemble des états simples
- Ensemble des états finaux.

Or notre automate est constitué que des états finaux, donc l’ensemble des états simples est vide.
(0.5)

Considérons
E0 et E1 à séparer (0.25)

E0 et E2 à séparer (0.25)

On obtient 2 ensembles tels que :
A={E0} et B={E1, E2} (0.5)

Considérons l’ensemble B
E1 et E2 à ne pas séparer (0.25)

Comme les états E0, E1 et E2 sont finaux donc A et B représentent des états finaux aussi. (0.25)
L’automate minimisé est : (0.5)
a, b
A

B

b

4- Grammaire qui engendre L(A)
a-

Si on considère l’automate déterministe :

Sa grammaire est définie par :
G=<{a,b}, {E0,E1,E2}, E0, P> avec P={ E0  b E1 / ; E1 bE1/a E2 / ; E2  bE1/a E2 / }
Une grammaire linaire à droite est une grammaire régulière à droite (c’est-à-dire de type 3), donc :
P={ E0  b E1 / /b ; E1 bE1/a E2 / b /a ; E2  bE1/a E2 /a /b }

b- Si on considère l’automate minimisé :
Sa grammaire est définie par :
G=<{a,b}, {A, B}, A, P> avec P={ A  b B / ; B b B/a B / }
Une grammaire linaire à droite est une grammaire régulière à droite (c’est-à-dire de type 3), donc :
P={ A  b B / / b ; B b B/a B / b /a }
5- Automate complémentaire : (2pts)
Pour complémenter un automate il faut qu’il soit déterministe et complet :
De la même manière, on complémente l’automate de la question 2 ou l’automate minimisé :
a- Si on considère l’automate de la Q2 :
Cet automate doit être compléter pour le complémenter :

b

Automate déterministe et complet :
b

E0

E1

a

a, b

b
a

P
E2
a

Automate complémentaire :

b
b

E0

E1

a

a, b

b
a

P
E2
a

(1.5)

b- Si on considère l’automate minimisé :
Complétons l’automate :

Complémentons l’automate :
a, b
a, b
A

A
a

a, b

P

b

a

B

a, b

P

b

B


Documents similaires


Fichier PDF td2
Fichier PDF etcd l2 2017 2018 thl
Fichier PDF correction td2
Fichier PDF les langages rguliers 1
Fichier PDF sujet thl 2016 2017
Fichier PDF notionsfondamentamles 2010 2011


Sur le même sujet..