serie1 THL 2010 2011 .pdf


Nom original: serie1-THL-2010-2011.pdfTitre: ExerciceAuteur: 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 5611 fois.
Taille du document: 217 Ko (2 pages).
Confidentialité: fichier public


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


Aperçu du document serie1-THL-2010-2011.pdf - page 1/2

Aperçu du document serie1-THL-2010-2011.pdf - page 2/2




Télécharger le fichier (PDF)


Télécharger
Formats alternatifs: ZIP



Documents similaires


serie1 thl 2010 2011
les bases de linformatique et de la programmation 914 pages
basesinfotout
txku3q0
rattrapage thl 2010 b
correction td2

🚀  Page générée en 0.012s