Correction TD3

1 / 27
Exercice 1

Considérons la grammaire G1 dont les productions sont les suivantes :

S→SaSaSbS | SaSbSaS | SbSaSaS | ε

1 - La grammaire est-elle régulière ? Justifier

Cette grammaire n’est pas régulière, elle n’est ni linéaire droite, ni

linéaire gauche.

2 - Trouver L(G1)

L(G1) = { w ∈{a, b}* | |w|a = 2 * |w|b}

3 - Donner une dérivation à gauche de la séquence abaaab.

SaSbSaS
S ⇒ SaSbSaS⇒ aSbSaS ⇒ abSaS ⇒ abaS ⇒ abaSaSaSbS ⇒
abaaSaSbS ⇒ abaaaSbS ⇒ abaaabS ⇒ abaaab

2 / 27
4 - La grammaire est-elle ambigüe ? Justifier.

Il suffit de trouver une autre dérivation à gauche pour la chaine

abaaab, ce qui permet d’obtenir deux arbres syntaxiques différents
pour une même chaîne par conséquent la grammaire est ambigüe.

3 / 27
Exercice 2

1 – L1 = { u ∈{a, b}* | |u|a = |u|b}

Automate à pile pour L1

ε,ε/Z0 ε,Z0/Z0

a,Z0/aZ0 a,a/aa
a,b/ε
b,Z0/bZ0 b,a/ε
b,b/bb

4 / 27
L3 = {ambncm , n≥0, m > 0}
Automate à pile pour L3

ε,a/a ε,a/a ε,Z0/Z0

a,Z0/aZ0 b,a/a c,a/ε

a,a/aa

5 / 27
L4 = {anbmcmd2n, n≥0 et m≥0}
Automate à pile pour L4

C
as
n = 0
n=0 0
m=

6 / 27
2 - Donner une grammaire qui le génère.

Productions de la grammaire pour L1 :L1 = { u ∈{a, b}* | |u|a = |u|b}

S →SaSbS | SbSaS | ε

Productions de la grammaire pour L3 : L3 = {ambncm , n≥0, m > 0}

A →aAc | aBc
B →bB | ε

Productions de la grammaire pour L4 : L4 = {anbmcmd2n, n≥0 et m≥0}

A →aAdd | B
B →bBc | ε

7 / 27
Exercice 3
1* + 10* 1* 0

Trouvant la grammaire de cet automate

8 / 27
G = {{A, B, C, D, E}, {0, 1}, P, A} P : l’ensemble des productions
suivantes :

A →1E| 1B
B →0B| 0D| 1C
C →0D| 1C
D →ε
E →1E| ε

9 / 27
 {w | w ∈{0, 1}* et w contient la sous-chaîne 00 ou 11}

G = {{A, B, C, D}, {0, 1}, P, A} P

l’ensemble des productions
1 B suivantes :

0
0 A→1A|0A|0B|1C
B→1A|0D
A 0,1 D 0,1 C→1D|0A
D→1D|0D|ε

0 1

1
C

10 / 27
{w | w ∈{0, 1}* et w ne termine pas par 01}

G = {{A, B, C}, {0, 1}, P, A} P

l’ensemble des productions
suivantes :
A→1A|0B|ε
B→1C|0B|ε
C→1A|0B

11 / 27
Exercice 4

2 - Grammaire G 2 n’est pas sous forme normale de Chomsky.

Rappel FNC :A → BC ou A →a
La grammaire comporte des productions ε qu’il faudra éliminer au
préalable.

U={S, A, B}, en plus S figure dans les parties droites. On ajoute un

nouvel axiome S’ et ses productions S’→S|ε

Élimination des productions ε :

Les productions suivantes seront ajoutés :

À partir de S→SaAb, on ajoute S→aAb, S→Sab, S→ab

À partir de S→bBaS, on ajoute S→baS, S→bBa, S→ba
À partir de A→bAa, on ajoute A→ba
À partir de B→aBb, on ajoute B→ab

12 / 27
On obtient la grammaire suivante équivalente à G2 :

S’→S|ε
S →SaAb|aAb|Sab|ab|bBaS|baS|bBa|ba
A →bAa|ba
B→aBb|ab

Mise sous forme de Chomsky.

Associer une variable à chaque terminal : C →a et D→b
Pour : S →SaAb|aAb|Sab|ab|bBaS|baS|bBa|ba
Devient :
S →SCAD|CAD|SCD|CD|DBCS|DCS|DBC|DC

Après transformation nous obtenons :

S →SE|CF|SG|CD|DH|DI|DJ|DC
E →CF
F →AD
G →CD
H →BI
I →CS
J →BC 13 / 27
Pour A →bAa|ba deveint
A →DAC|DC
Après transformation nous obtenons :
A →DK|DC
K →AC

Pour B→aBb|ab devient

B→CBD|CD
Après transformation nous obtenons :
B →CL|CD
L →BD

Enfin S’ →S|ε On remplace S par tout son corps on obtient

S’ →SE|CF|SG|CD|DH|DI|DJ|DC| ε

3 - Montrer que la grammaire G2 est ambigüe.

Faire un test avec le mot : baab

14 / 27
4 - Éliminer la récursivité à gauche dans chacune des ces
grammaires.

La grammaire G2 est récursive à gauche au niveau de de la règle

S→SaAb

Grammaire G2
S →SaAb|bBaS|ε
A →bAa|ε
B →aBb|ε
Nous devons éliminer la récursivité après l’élimination des
productions ε. Il n’y a pas de cycles
S’→S|ε
S →SaAb|aAb|Sab|ab|bBaS|baS|bBa|ba
A →bAa|ba
B→aBb|ab

15 / 27
Nous choisissons l’ordre de traitement suivant : S’, S, A, B
Traitement de S’→S|ε : pas de récursivité directe.

Traitement de S→SaAb|aAb|Sab|ab|bBaS|baS|bBa|ba
Rappel
A → Aα|β
A → βA’
A’ → αA’|ε

S →aAbS’’ |abS’’|bBaSS’’|baSS’’|bBaS’’|baS’’
S’’ →aAbS’’|abS’’|ε

Traitement de A : pas de remplacement pas de récursivité à

gauche.
Traitement de B : pas de remplacement pas de récursivité à
gauche.

16 / 27
Grammaire G3
S →ST|SSb|TS|a
T →Sa|Tb|ε

Cette grammaire est récursive à gauche au niveau :

S →ST et T →Tb

Il faut tout d’abord éliminer les productions ε et les cycles :

Pour : S →ST|SSb|TS|a : on obtient

S →ST|SSb|TS|a|S

Pour T →Sa|Tb|b|ε : on obtient

T →Sa|Tb|b
La grammaire équivalente à G3 sans ε productions ε est :

S →ST|SSb|TS|a|S
T →Sa|Tb|b

17 / 27
Cette grammaire présente un cycle, il faut alors éliminer les
productions unitaires, la grammaire devient:

S →ST|SSb|TS|a
T →Sa|Tb|b

Éliminons maintenant la récursivité gauche. Nous choisissons

l’ordre suivant : S, T

Pour : S →ST|SSb|TS|a

S →TSS’|aS’
S’→TS’|SbS’|ε

Pour : T →Sa|Tb|b
Remplacement de S dans les productions de T :
T→TSS’a|aS’a|Tb|b on obtient :

T→aS’aT’|bT’
T’ →SS’aT’|bT’|ε
18 / 27
La grammaire G4
S →S ∨ T | T
T →T ∧ F | F
F → ¬ F| (S)| x | y

n’a ni de productions ε, ni de cycle. Elle est récursive à gauche au

niveau de des productions de S (S →S ∨ T) et de T (T →T ∧ F).
Nous procédons à l’élimination de la récursivité. Nous choisissons
l’ordre suivant : S, T, F

Pour S →S ∨ T | T : on obtient
S → TS’
S’ →vTS’|ε

Pour T →T ∧ F | F : Pas de remplacements. Nous éliminons la

récursivité directe. On obtient
T →FT’
T’ →∧FT’|ε

Pour F → ¬ F| (S)| x | y Pas de récursivité .

19 / 27
5 Factoriser à gauche chacune de ces grammaires
Factorisation de G2

S’ →S|ε
S →aAbS’’ |abS’’|bBaSS’’|baSS’’|bBaS’’|baS’’
S’’ →aAbS’’|abS’’|ε
A →bAa|ba
B→aBb|ab

Factorisation au niveau de S.
S →aC|bD
C→AbS’’|bS’’
D→BaE|aE
E→SS’’|S’’

Factorisation au niveau de S’’

S’’ →aF|ε
F→AbS’’|bS’’

20 / 27
Factorisation au niveau de A. A →bAa|ba
A→bG
G→Aa|a

Factorisation au niveau de B. B→aBb|ab

B→aH
H→Bb|b

Factorisation de G3
S →TSS’|aS’
S’→TS’|SbS’|ε
T→aS’aT’|bT’
T’ →SS’aT’|bT’|ε
On ne peut factoriser qu’au niveau de T :
T→aA|bT’
A→S’aT’

Aucune factorisation au niveau de G4.

21 / 27
6 - Donner la grammaire générant L(G2)*
Grammaire G2

S →SaAb|bBaS|ε
A →bAa|ε
B →aBb|ε
Grammaire G2*
S’→SS’|ε
S →SaAb|bBaS|ε
A →bAa|ε
B →aBb|ε

22 / 27
7 - Donner la grammaire générant L(G4) U L(G3)
Grammaire G4
S →S ∨ T | T
T →T ∧ F | F
F → ¬ F| (S)| x | y

Grammaire G3
S →ST|SSb|TS|a
T →Sa|Tb|ε

Grammaire G4 U G3 :
Renommer S et T dans G3 en S3 et T3 . Les productions de G3
deviennent :
S3 →S3T3|S3S3b|T3S3|a
T3 →S3a|T3b|ε

23 / 27
Les production G3 U G4 sont
Su →S|S3
S3 →S3T3|S3S3b|T3S3|a
T3 →S3a|T3b|ε
S →S ∨ T | T
T →T ∧ F | F
F → ¬ F| (S)| x | y

24 / 27
8 - Construire un automate à pile acceptant par état final pour la
grammaire G3 , le transformer en un automate à pile acceptant par
pile vide.

Automate acceptant L(G3) par état final

ε,S/ST ε,T/Sa a,a/ε

ε,S/SST ε,T/Tb b,b/ε
ε,S/TS ε,T/ε
ε,S/a

ε,Z0/SZ0 ε,Z0/Z0

25 / 27
Transformation de l’automate pour qu’il accepte par pile vide

26 / 27
9 - Construire un automate à pile acceptant par pile vide pour la
grammaire G4 , le transformer en un automate à pile acceptant
par état final.
Automate acceptant L(G4) par pile vide

Transformation de l’automate pour qu’il accepte par état final

ε,Z0/SZ0 ε,Z0/Z0

27 / 27