Théorie des langages : Td 3 langages de programmation
Télécharger PDFUniversité de Technologie de Compiègne
NF11 - Théorie des Langages de Programmation
TD3 : Corrigé
Exercice 11. On donne deux dérivations gauche du motabab:
D1 :S=⇒LM aSbS=⇒LM abSaSbS=⇒LM abaSbS=⇒LM ababS=⇒LM abab
D2 :S=⇒LM aSbS=⇒LM abS=⇒LM abaSbS=⇒LM ababS=⇒LM abab
la grammaire est ambiguë, car Il existe deux dérivations gauches pour le motabab. 2. On donne deux dérivations droite pour le motabab:
D1 :S=⇒RM aSbS=⇒RM aSb=⇒RM abSaSb=⇒RM abSab=⇒RM abab
D2 :S=⇒RM aSbS=⇒RM aSbaSbS=⇒RM aSbaSb=⇒RM aSbab=⇒RM abab
3. Les arbres de dérivations sont donnés par les figures (3) et (3).
Figure1 – D1 : Arbre de dérivation
Figure2 – D2 : Arbre de dérivation
4. Cette grammaire génère le langageLcomposé de toutes las chaines suraetb
tel que le nombre deaest égal au nombre deb.
Démonstration :
Soit l’hypothèse suivante, H : Le langageLest composé de n’importe quel mot
suraetbtel que le nombre deaest égale au nombre deb. On décompose cette
hypothèse en deux parties :
— Soitwn un mot du langageL, composé dencaractères. On note par|wn |a et|wn |b le nombre deaet deb, respectivement, dans le motwn .H 1:|w n| a=|w n| b
, en conséquence n est pair.1 —H2 : La grammaire génère tous les mots possibles suraetbtel que la
dernière condition est vraie.
Vérification :
— pourn= 0la grammaire peut générer.
— pourn= 2la grammaire peut générer :—S=⇒ LMaSbS=⇒ LMabS=⇒ LMab —S=⇒LM bSaS=⇒LM baS=⇒LM ba
Il est à noter qu’il y a 4 mots possibles suraetbde longueur 2 :aa, ab, ba, bb.
Seulsabetbavérifient la conditionsH1 . En conséquence :H1 etH2 sont
vraies pourn= 0etn= 2.
On suppose queHest vraie (en particulierH1 etH2 ) jusqu’à l’ordren.
Démonstration : Dans la suite on démontre H pour l’ordren+ 1.
Les motswn+2 sont obtenus comme suit :—w n+2=aw lbw m
(en utilisantS−→aSbS)—w n+2=bw law m
(en utilisantS−→bSaS)
Il est clair quel+m=n. En utilisant l’hypothèse de récurrence surletm,
on remarque queH1 est vraie pourwl etwm . On a : |wn+2 |a = 1 +|wl |a +|wm |a |wn+2 |b = 1 +|wl |b +|wm |b On conclut que|wn+2 |a =|wn+2 |b car|wl |a =|wl |b et|wm |a =|wm |b (Hypothèse
de récurrence).
Concernant la deuxième partie de la démonstration Supposons qu’il existe un
motWden+ 2caractères ayant le même nombre deaque deb, qui n’est pas
généré par la grammaire.
Supposons queWcommence para(Le même raisonnement est valide pour un
mot qui commence parb, ce cas ne sera pas détaillé dans la démonstration).
Soitkle plus petit indice d’un caractèrebtel que le nombre deadansW[1..k]
est égal au nombre debdansW[1..k](oùW[1..k]est la chaîne formée par les
kpremières caractères de la chaîneW).
Exemple : considérons le mot "aababbab", on aurak= 6,W[1..6] = ”aababb”.
DansW[1..6]le nombre deaest égal au nombrebest égal à 3.
En tenant compte que le premier caractère deWest égal àaet que lek`eme caractère est égal àbon peut récrireWde la manière suivante :W=aw lbw m
,avecl=k−2, m=n−k
SiWexiste alorswl et/ouwm ne sont pas générés par la grammaire. Absurde,
on contredit l’hypothèse de récurrence pourwl et/ouwm où H est vrai car
l, m≤n.
Exercice 2Précision : l’ensemble des terminaux de la grammaire estT={(,), a, b,∗,|}
1. la grammaire génère des expressions régulières exclusivement suraetb(impos-
sible d’avoir). L’expression peut contenir les méta symboles parenthèses et
peut être composée des 3 opérateurs : concaténation, disjonction et fermeture.2 Démonstration :Soitw k
un mot du langage engendré par la grammaire obtenu après avoir
appliquékrègles de production.
H :wk est une expression régulière définie suraetb. De plus,wk peut conte-
nir les méta symboles parenthèses et peut être composée des 3 opérateurs :
concaténation, disjonction et fermeture.
Vérification : On remarque que la grammaire génèrew1 =aetw1 =bdeux
expression régulières obtenues après avoir appliqué une règle de production (
une des deux dernières).
On Suppose queHVraie,∀k≤n.
On démontre queHest vraie pourk=n+ 1. En utilisant les 4 premières
règles de production de la grammaire, on remarque que :w n+1= w iw j
,∀i, j >0;i+j=nw i|w j
,∀i, j >0;i+j=nw i∗,i=n (wi )i=n(1) On note que H est vraie pourietj. A partir de (1), on conclut que quewn+1 est bien une expression régulière vérifiant les conditions listées ci-dessus.
2. On considère le motaba, et on donne ces deux dérivations :
D1 :R=⇒LM RR=⇒LM aR=⇒LM aRR=⇒LM abR=⇒LM aba(2)
D2 :R=⇒LM RR=⇒LM RRR=⇒LM aRR=⇒LM abR=⇒LM aba(3)
Exercice 31. L’ensemble des terminaux de cette grammaire estT={∗, /,+,−,(,), id, nb}
2. Soit la grammaireG= (T={∗, /,+,−,(,), id, nb}, V={E, T, F}, E, P),avecP: E→E+T|E−T|T
T→T∗F|T /F|F
F→(E)|id|nb
Attention la grammaire suivanteG1 , ou toute grammaire équivalente, ne gère
pas la priorité de∗et/par rapport à+et−:
Soit la grammaireG1 = (T={∗, /,+,−,(,), id, nb}, V={E}, E, P), avecP:
E→E+E|E−E|E∗E|E/E
E→(E)|nb|id
La grammaireG1 est ambiguë. On donne deux dérivation gauche du mot
”id+id∗id”:
D1 :E=⇒LM E+E=⇒LM id+E=⇒LM id+E∗E=⇒LM id+id∗E=⇒LM id+id∗id
D2 :E=⇒LM E∗E=⇒LM E+E∗E=⇒LM id+E∗E=⇒LM id+id∗E=⇒LM id+id∗id3 Si on remplace tous lesidpar la valeur5, le résultat deD1est30alors que
le résultat deD2est50. DansD2la priorité de∗par rapport à+n’est pas
vérifiée.
3. Il existe des techniques pour obtenir une grammaire non récursive à gauche.
On les abordera dans les prochains cours.
4. On donne l’arbre représenté dans la figure 4
Figure3 – Arbre de dérivation de la question 4
Exercice 4Dans une forme FNC, les règles de productions sont sous la forme suivante :A→BC|a Avecaest un terminal etA, BetCdes variables. De plus, seul l’axiome peut générer
le mot vide.
1. On considère la grammaireG= (T{a, b}, V={S, A, B}, S, P), avecP:S→A|Bbb A→aB|bS|
B→ABb|Bb|
—Étape 1 :On Remarque queAetBpeuvent générer le mot vide. On
supprimeA→etB→. Il faudra modifier la grammaire de manière à
prendre en compte cette modification. Par exemple, si on considèreS→
Bbb, en tenant en compte que B peut générer le mot vide et qu’on supprime
la règlesB→,S→Bbbse transforme enS→Bbb|bb4 On obtient la grammaireG= (T{a, b}, V={S, A, B}, S, P), avecP:
S→A|Bbb|bb|
A→aB|bS|a
B→ABb|Bb|b|Ab
—Étape 2 :On Supprime la règle de productionS→A. On obtient la
grammaireG= (T{a, b}, V={S, A, B}, S, P), avecP:
S→aB|bS|a|Bbb|bb|
A→aB|bS|a
B→ABb|Bb|b|Ab
—Étape 3 :On modifie les règles de productions où à droite il y a une
combinaison de terminaux et de non terminaux. On obtient la grammaire
G= (T{a, b}, V={S, A, B,C,D}, S, P), avecP:C→a D→b
S→CB|DS|a|BDD|DD|
A→CB|DS|a
B→ABD|BD|b|AD
—Étape 4 :On modifie les règles de productions où à droite il y a plus de 2
variables. On obtient : la grammaireG= (T{a, b}, V={S, A, B, C, D,X}, S, P),avecP: X→BDC→a D→b
S→CB|DS|a|XD|DD|
A→CB|DS|a
B→AX|BD|b|AD
La grammaire obtenue est bien sous formeF N C.
2. Les règles de production d’une grammaire de type 2 s’écrivent sous le format
suivant :
A→α, α∈(V∪T)∗ On propose un algorithme à 4 étapes qui permet d’obtenir une grammaire
équivalente sous forme FNC.
—Étape 1 :Pour chaque variableA∈V, tel queA6=Set queApeut
générer le mot vide :
— supprimerA→
— pour chaque règle de production sous la forme :
B→αAβ,avecα, β∈(V∪T)∗ ajouter l’alternative :B→αβ 5
Répéter cette étape tant qu’il existe au moins une variable différente de
l’axiome qui peut générer le mot vide.
À la fin de cette étape on obtient une grammaire tel que les règles de
productions s’écrivent sous le format suivant :
S→α, α∈(V∪T)∗ A→β, A6=S, β∈(V∪T)+ —Étape 2 :Pour chaque règle de production sous la formeA→B:
— SupprimerA→B.
— Pour chaque règle de productionB→α, on ajoute la règle de produc-
tionA→α.
Répéter cette étape tant qu’il existe une règle de production sous la formeA→B. À la fin de cette étape, on obtient une grammaire tel que les règles de
productions s’écrivent sous le format suivant. Soitα=T|(V∪T)(V∪T) +. S→|α
A→α, A6=S
—Étape 3 :Pour chaque règle de production sous la formeA→α, α=(V∪T) ∗t(V∪T) +|(V∪T) +t(V∪T) ∗
avect∈T:
— ajouter la règle de productionX→t
— remplacer dansα, tparX
Répéter cette étape tant qu’il existe une règle de production sous la forme
A→α, α= (V∪T)∗ T(V∪T)+ |(V∪T)+ T(V∪T)∗ .
À la fin de cette étape, on obtient une grammaire tel que les règles de
productions s’écrivent sous le format suivant. Soitα=T|V V+ .S→|α A→α, A6=S
—Étape 4 :Pour chaque règle de production sous la formeA→BCα, avecα=V +: — ajouter la règle de productionY→BC
— remplacer dansA→BCαparA→Y α
Répéter cette étape tant qu’il existe une règle de production sous la forme
A→BCα, avecα=V+ .
À la fin de cette étape, on obtient une grammaire tel que les règles de
productions s’écrivent sous le format suivant. Soitα=T|V V.S→|α A→α, A6=S
La grammaire obtenue est sous forme FNC.
6