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



serie1 THL 2010 2011 .pdf


Nom original: serie1-THL-2010-2011.pdf
Titre: Exercice
Auteur: 4A

Ce document au format PDF 1.4 a été généré par Writer / OpenOffice.org 3.1, et a été envoyé sur fichier-pdf.fr le 20/02/2011 à 18:44, depuis l'adresse IP 41.201.x.x. La présente page de téléchargement du fichier a été vue 5302 fois.
Taille du document: 217 Ko (2 pages).
Confidentialité: fichier public




Télécharger le fichier (PDF)









Aperçu du document


Département Informatique
USTHB

Théorie des langages
Série 1

Année 2010­2011

Exercice 1
Soit X un alphabet et soient a, b ∈ X et w ∈X*.  
Montrer que si wa=bw  alors  a=b.

Exercice 2 
Soit X un alphabet et soient x, y, w ∈X*.  
1. Vérifier si : Mir(xy)=Mir(x)Mir(y)
2. Montrer que Mir(xy)=Mir(y)Mir(x)

Exercice 3 

Donner les grammaires générant les langages suivants :
1.   L'ensemble des nombres binaires
1. L'ensemble des nombres binaires  sans  0 inutiles en tête
2. L’ensemble des nombres binaires de longueur impaire.  
3. Les identificateurs du langage C.
4. Les nombres décimaux éventuellement signés.
5. Les nombres décimaux divisibles  par 5.
6. Les chaînes de caractères du langage Pascal. Une chaîne de caractères en Pascal 
est une suite de caractères encadrée par des apostrophes. Le caractère ’ est lui 
représenté par deux apostrophes consécutives.  
7. Les expressions arithmétiques parenthésées formées avec +, ­, ÷,  *,  (, ) et les 
nombres formés sur 0,1, …, 9

Exercice  4  

Donner la grammaire engendrant des programmes de la forme :
 
Program test
a : integer ;
b : float ;
begin
a:=1;
b :=3 ;
if a>2 then a :=4 ; else begin b :=1 ; a:=3 end; endif ;
end .
Les seules instructions autorisées sont l’affectation et la conditionnelle. L’alphabet terminal 
est : {program, integer, float, begin, end, if, then, else, endif, :, :=, >, =, idf, constante}où idf 
et constante représentent respectivement un identificateur et une constante.

Exercice 5
Donner les grammaires générant les langages suivants en donnant le type de la grammaire :
1. L1= {ai(ab)jck, i>=0, k≥1 et j≥2}
2. L2 ={ a2i+3b3j+1 / i, j≥0}
3. L3 ={w ∈{a, b, c}* / |w|c =2p, p≥0 }
4. L4={ai bj /  j≥i≥0}
5. L5= { am bn cp / m+2n=p}

1

Département Informatique
USTHB

6.
7.
8.
9.
10.
11.
12.
13.

Année 2010­2011

Théorie des langages
Série 1

L6={a2mbn+1ck / m≥n+k, n, m ≥0 et k ≥2}
L7={ am bn cp /m≥n ou n≥2p}
L8={ am bn / m≠n }
L9={w∈{0,1}* / w divisible par 3}
 L10={w∈{a, b, c}* / |w|a+|w|c est divisible par 3}
 L11={w∈{a, b, c}* / |w|a+2|w|c ≡ 1[3]}
L12={wwr / w ∈ {a, b}*}
L13={ w ∈{a,b}*/ |w|a= |w|b}

     

Exercice 6
Pour chacune des grammaires suivantes, donner son type et le langage qu'elle génère.
1.  G1=({a, b}, {S}, S, P1) où P1 est 
  
   S → aaSb /  ab / bb
 
   
2. G2 =({a, b, c}, {S}, S, P2) où P2 est 
               S  → aSa / aSb  / c
3.  G3 =({a, b}, {S,  A}, S, P3) où P3 est 
           S → aSa / bA / A
           A → Ab / ε 
4.    G4 =({u, x, w}, {S,  U, L, G}, S, P4) où P4 est 
 S → ULG

     U → uU / ε
          L → wLG / ε
         G → xG / x

Exercice 7  (Interrogation 2009­2010)
I. Construire une  grammaire pour chacun  des langages suivants :
1. L1={anwb2m / n, m>0 et w∈{a, b}*}
2. L2={anwb2n / n>0 et w∈{a, b}*}
II. Soit la grammaire G=({a, b}, {S, A, B}, S, P) où P est défini par :
S → aaS / A / aB
A→ bbA / ε
B → bBb / b
1. Quel est le type de la grammaire G ?  Justifier
2. Donner le langage L(G) généré par cette grammaire. Justifier votre réponse.

Exercice 8 (Rattrapage 2009­2010)

Soit la grammaire G=({a, b}, {S, A, B}, S, P) où P est défini par :
             S → abS / A    
            A→ aAB / ε

     B → bbB / bb

1. Quel est le type de la grammaire G ?  Justifier
2.. Donner le langage L(G) généré par cette grammaire. Justifier votre réponse.

2


serie1-THL-2010-2011.pdf - page 1/2
serie1-THL-2010-2011.pdf - page 2/2

Documents similaires


serie1 thl 2010 2011
sujet thl 2016 2017
notionsfondamentamles 2010 2011
une petite idee sur la logique en mathematiques
td2
etcd l2 2017 2018 thl


Sur le même sujet..