Faculté des Sciences de Tunis

Département des Sciences de l'Informatique

 

Examen Trimestriel

 

 

Matière :Théorie des langages et compilation

Section :1F4

Durée :lh 30

Date :15 Décembre 2003

Enseignante : Leila JEMNI BEN AYED

 

 

 

 

Exercice 1. (6 points : 2 — 2 - 2)

Soit le langage L suivant :

L {w Є {a, b}* / |w|b,= 2k + 1 , k> 0}

I) Déterminer une grammaire non contextuelle G qui génère L,

2) Montrer que L est régulier.— (

3) Déterminer une grammaire GI qui génère le langage :

L++ {w Є {a, b}*/ |w|a 2k + 1, k>0}

Exercice 2. (4 points)

Construire un automate à pile à critère pile vide qui reconnaît le langage suivant :

L = {aⁿb²ⁿ⁺¹ck / n>0, k>0}.

Exercice 3. (6 points)

Déterminer une grammaire qui génère des expressions arithmétiques où logiques en utilisant

les terminaux suivants : les identificateurs alphanumériques, les constantes numériques, les

opérateurs logiques ( Et Ou, NON les opérateurs de c o m p a r a i s o n { > , >= , < , < = , , = }

l e s  opérateurs arithmétiques( +,*,-,/) et les parenthèses {(, )}.

Exemple d'expressions :

-(a + b) / c * b

-(a<x ET x<b)

-(a + b) / c >= 34

- trouve

Exercice 4. (4 points)

Construire un automate fiai déterministe minimal qui accepte le langage représenté par

l'expression régulière : (a+b)*a*b*+ sur l'alphabet {a, b}.