Théorie des langages et Compilation – Chapitres 3 et 4

e

e

d

d

d

d

d

fi

fi

fi

˛

˛

e

fi

e

fi

e

fi

e

˛

˛

III.4. Langages réguliers et grammaires

régulières

Exercice 1 : Soit la grammaire régulière G ayant les règles de

production suivantes, construire un automate A / L(G) = L(A)

G = (V, T, A, R)/ V = {A, B}, T = {a, b}, R = {A fi

bB | aA|e

e , B fi

bB |e

e }

Corrigé Exercice 1:

bB

bB

aA

bB

A fi

A fi

A fi

A fi

B fi

B fi

a

A

b

b

B

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

17

fi

fi

fi

fi

fi

fi

e

e

fi

fi

fi

e

e

fi

fi

fi

fi

fi

fi

fi

fi

fi

e

e

e

e

fi

fi

fi

fi

fi

fi

e

e

e

e

III.4. Langages réguliers et grammaires

régulières

• Conversion automate/grammaire

Soit M = (Q, X, d

d , q0, F) un automate fini,

On définit une grammaire G / L(G) = L(M) comme suit:

G = (V, T, S, R)/

V = Q

V = Q

T = X

S = q0

R = {p fi

xq / (p, x, q) ˛

/ q ˛

{q fi

d } ¨

F}

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

18

d

d

fi

fi

fi

˛

˛

˛

d

d

d

¨

¨

¨

e

fi

e

fi

e

fi

e

˛

˛

˛

III.4. Langages réguliers et grammaires

régulières

Exercice : Soit l’automate fini A suivant :

Exercice : Soit l’automate fini A suivant :

A = (Q, X, d , q0, F) / Q = {A, B}, X = {a, b}, d = {(A, a, A), (A, b, B), (B, b, B)}, q0 = A,

F = {A, B}

Construire une grammaire régulière G / L(G) = L(A)

Corrigé Exercice 2:

Corrigé Exercice 2:

G = (V, T, A, R)/ V = {A, B}, T = {a, b}, R = {A fi

bB | aA|e , A fi

bB |e }

a

b

b

A

B

bB

aA

bB

A fi

A fi

A fi

B fi

B fi

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

19

fi

fi

fi

fi

fi

fi

fi

fi

fi

e

e

e

e

fi

fi

fi

fi

fi

fi

e

e

e

e

III.5. Les formes normales des

grammaires

III.5.1. Forme standard binaire (CHOMSKY)

C’est la forme des règles de production suivantes :

a

BC ; A fi

A fi

où

où

A, B, C ˛ V et a ˛ X ¨

{e }

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

20

fi

fi

fi

fi

fi

fi

III.5. Les formes normales des

grammaires

Exercice 1 : Soit la grammaire G suivante. Construire une grammaire G’ sous

forme de CHOMSKY qui génère L(G) (le langage généré par G)

G = ({S, A, B}, {a, b}, S, R)

R = {

S fi

A fi

A fi

A fi

A fi

bA,

a,

aS,

bAA,

bAA,

S fi

B fi

B fi

B fi

B fi

aB,

b,

bS,

aBB }

aBB }

Corrigé Exercice 1: La forme standard binaire associée aux règles de production de la

grammaire G est :

R’= {

C1A,

b,

a,

C2S,

a,

C1C3,

AA,

C2B,

b,

C1S, }

La mise en forme standard binaire de la grammaire G donne la grammaire G’

G’ = ({S, A, B, C1, C2, C3, C4}, {a, b}, S, R’)

S fi

C1 fi

A fi

A fi

C2 fi

A fi

C3 fi

S fi

B fi

B fi

C2C4,

BB,

B fi

C4 fi

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

21

III.5. Les formes normales des

grammaires

III.5.2. Forme standard de GREIBACK

C’est la forme des règles de production suivantes :

av

A fi

où

où

a ˛ X, A ˛ V, v ˛ V*

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

22

fi

fi

fi

III.5. Les formes normales des

grammaires

Exercice 2: Soit la grammaire G suivante. Construire une

grammaire G’ sous forme GREIBACK qui génère L(G)

G = ({A1, A2, A3}, {a, b}, A1, R)

R = {

A1 fi

A3 fi

A3 fi

A2 fi

A4 fi

A3 fi

A1 fi

A3 fi

A3 fi

A2A3,

A4A3,

A4A3,

aA3,

b,

b }

aA3A3

b A3

b }

Corrigé Exercice 2: La forme standard de GREIBACK associée est :

R’= {

La mise en forme standard de GREIBACK de la grammaire G donne la grammaire G’

G’ = ({A1, A3}, {a, b}, A1, R’)

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

23

IV. Les grammaires non contextuelles

Plan

IV.1. Définition d’une grammaire non

contextuelle

contextuelle

IV.2. Dérivation

IV.3. Langage généré par une grammaire

IV.4. Langage hors contexte

IV.5. Dérivation, arbre et ambiguïté

IV.6. Propriétés des langages non

contextuels

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

24

IV.1. Définition d’une grammaire non

contextuelle (GNC)

Une grammaire non contextuelle G est un quadruplet:

G = (V, T, S, R)

Où

V est un alphabet non terminal

T est un ensemble de terminaux

T est un ensemble de terminaux

R est l’ensemble des règles de production de la forme

A fi

fi U / A ˛ V et U ˛

(V ¨

T)*

S est l’axiome de la grammaire (Symbole de départ)

(S ˛ V)

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

25

fi

fi

IV.2. Dérivation

• U ⇒ V dénote la dérivation de V à partir de U

• U ⇒ V ssi il existe des chaines x, y, t ˛

telles que : U = x Ay, V = x t y et A fi

G

(V¨

t

T)* et A ˛ V

Exemple

Exemple

G = ({S}, {a, b}, S, {S fi

S ⇒ aSb ici

U = S

V = aSb

aSb ⇒ aaSbb ici U = aSb

aSb |e })

V = aaSbb

k

U ⇒ V

(cid:219) U ⇒ U1

⇒ U2

⇒… Uk = V

x = e et y = e

A = S et t = aSb

x = a et y = b

A = S et t = aSb

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

26

IV.3. Langage généré par une

grammaire

• La relation ⇒ est la fermeture réflexive et transitive de ⇒

G

G

*

*

S ⇒⇒⇒⇒ w

k

$ k ‡

‡ 1 / S ⇒⇒⇒⇒ w

Par exemple S ⇒⇒⇒⇒ aabb Puisque S ⇒aSb ⇒ aaSbb ⇒ aabb

Par exemple S ⇒⇒⇒⇒ aabb Puisque S ⇒aSb ⇒ aaSbb ⇒ aabb

*

Le langage généré par une grammaire G est L(G)

L(G) = { w

*

X* / S ⇒ w

}

aabb ˛

L(G) par ce que S ⇒⇒⇒⇒ aabb

*

L(G) par ce que S ⇒⇒⇒⇒ e

*

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

27

w

w

w

(cid:219)

(cid:219)

(cid:219)

(cid:219)

$

$

$

‡

‡

w

w

w

˛

e

e

e

e

˛

e

e

e

IV.4. Langage hors contexte ou

indépendant du contexte

Un langage L est dit non-contextuel

ssi

Il existe une grammaire non-contextuelle G

Il existe une grammaire non-contextuelle G

telle que

telle que

L(G) = L

Si LR est l’ensemble des langages réguliers et LIC est l’ensemble des

langages indépendant du contexte, alors on a

LR (cid:204)

LIC

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

28

(cid:204)

(cid:204)

(cid:204)

IV.4. Langage hors contexte ou

indépendant du contexte

Exemple :

G = (V, X, E, R)

V = {T, F, E}

X = {x1, x2, +, *, (, )}

R = { E fi

E fi

E fi

T fi

T fi

F fi

F fi

F fi

E + T

T

T

T *F

F

(E)

x1

x2

}

(1)

(2)

(2)

(3)

(4)

(5)

(6)

(7)

G génère la chaine (x1x2+x1)(x1+x2) par la

dérivation suivante

E ⇒⇒⇒⇒ T (2) ⇒⇒⇒⇒ TF (3) ⇒⇒⇒⇒ FF (4)

⇒⇒⇒⇒ (E)F (5) ⇒⇒⇒⇒ (E+T)F (1)

⇒⇒⇒⇒ (T+T)F (2) ⇒⇒⇒⇒ (TF+T)*F (3)

⇒⇒⇒⇒ (FF +T)F (4) ⇒⇒⇒⇒ (x1F+T)F (6)

⇒⇒⇒⇒ (x1x2+T)F (7) ⇒⇒⇒⇒ (x1x2+F)F (4)

⇒⇒⇒⇒ (x1x2+T)F (7) ⇒⇒⇒⇒ (x1x2+F)F (4)

⇒⇒⇒⇒ (x1x2+x1)F (6) ⇒⇒⇒⇒ (x1x2+x1)(E) (5)

⇒⇒⇒⇒ (x1x2+x1)(E+ T) (1)

⇒⇒⇒⇒ (x1x2+x1)(T+ T) (2)

⇒⇒⇒⇒ (x1x2+x1)(F+ T) (4)

⇒⇒⇒⇒ (x1x2+x1)(x1+ T) (6)

⇒⇒⇒⇒ (x1x2+x1)(x1+ F) (4)

⇒⇒⇒⇒ (x1x2+x1)(x1+ x2) (7)

L(G) est (ou bien G génère) l’ensemble des expressions arithmétiques

parenthèsées utilisant x1, x2 et les opérateurs arithmétiques + et *.

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

29

IV.4. Langage hors contexte ou

indépendant du contexte

Exercice :

1) Construire une grammaire G qui génère des expressions booléennes sur les

nombres entiers, les opérateurs arithmétiques {+, *}, les opérateurs booléens {et,

ou, non} et les opérateurs relationnels {>, <, = }

2) Vérifier que le mot (nb + nb) > nb est généré par la grammaire

2) Vérifier que le mot (nb + nb) > nb est généré par la grammaire

Corrigé :

G = (V, X, Ea, R)

V = {Ea, Eb, Er}

X = {nb, +, *, (, ) , >, <, = , et, ou, non} où nb représente un nombre entier.

R = { Ea fi

Er fi

Eb fi

Ea + Ea | Ea * Ea | nb | (Ea)

Ea > Ea | Ea < Ea | Ea= Ea

Er | non Eb | Eb et Eb | Eb ou Eb

}

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

30

Exemple d’un langage indépendant du

contexte (LIC)

Lemme1

Tout langage L hors-contexte tel que e

Tout langage L hors-contexte tel que e

L

L

peut être engendré par une grammaire

forme normale de

hors-contexte sous

GREIBACK

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

31

ˇ

ˇ

IV.5. Dérivation, arbre et ambiguïté

A chaque dérivation, on associe un arbre dont:

-La racine est étiquetée par le symbole de départ de la grammaire

-A un nœud étiqueté A, on associe les fils X1X2… Xn si la règle Afi

appliquée.

X1X2…Xn a été

-Exemple

-Exemple

S fi

A fi

B fi

AB

a

b

Pour le mot ab, on a deux dérivations possibles :

1) S ⇒ AB ⇒ aB ⇒ ab

2) S ⇒ AB ⇒ Ab ⇒ ab

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

32

IV.5. Dérivation, arbre et ambiguïté

1) S ⇒ AB ⇒ aB ⇒ ab

2) S ⇒ AB ⇒ Ab ⇒ ab

Ces deux dérivations ne diffèrent que par l’ordre d’application des règles. En

conséquence, on fait correspondre le même arbre.

S

A

B

a

b

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

33

IV.5. Dérivation, arbre et ambiguïté

Dérivation la plus à gauche (lpg)

*

Pour un arbre donné correspondant à la dérivation : A ⇒ w

Où w

X*, il existe une dérivation unique ayant la propriété suivante :

⇒ w

0

⇒ w

1

2

⇒…… ⇒ w

n = w

A = w

et

et

i = 0, …, n-1 : w

i = ui Ai yi

i+1 = ui Zi yi

(Ai

Zi) ˛ R ; ui

˛ X*

On l’appelle la dérivation la plus à gauche

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

34

˛

"

w

fi

fi

fi

fi

IV.5. Dérivation, arbre et ambiguïté

Dérivation la plus à gauche (Exemple)

Soit G = ({S, A}, {a, b}, S, R) R = {S fi

Soit w = ababa

aAb, S fi

a, S fi

abSbS, A fi

bS}

Au mot w

, correspond la dérivation la plus à gauche suivante :

S ⇒ abSbS ⇒ ababS ⇒ ababa

L’arbre correspondant est le suivant:

a

b

La dérivation S ⇒ abSbS ⇒ abSba ⇒ ababa

N’est pas une dérivation la plus àgauche

S

S

a

b

S

a

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

35

IV.5. Dérivation, arbre et ambiguïté

Lemme 2

Pour tout mot d’un langage L(G), il

existe une dérivation la plus à gauche

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

36

IV.5. Dérivation, arbre et ambiguïté

Exemple

Soit G = ({S, A}, {a, b}, S, R) R = {S fi

Le mot w = abababab ˛

Une dérivation possible est qui n’est pas la plus à gauche:

aAb, S fi

a, S fi

L(G)

abSbS, A fi

bS}

L’arbre de dérivation est :

a

b

S

S

a

S ⇒ abSbS

⇒ abSbaAb

⇒ abSbaAb

⇒ abSbabSb

⇒ abSbabab

⇒ abababab

(3)

(1)

(1)

(4)

(2)

(2)

b

S

a

A b

b

S

Leila Jemni Ben Ayed

a

Théorie des Langages et Compilation - 2013

37

IV.5. Dérivation, arbre et ambiguïté

a, S fi

aAb, S fi

Exercice :

Soit une grammaire avec les règles de production suivantes :

R = {S fi

abSbS, A fi

1) Donner une dérvation la plus à gauche du mot abababab

2) Construire un arbre associé à cette dérivation

3) Construire deux dérivations les plus à gauche pour le mot abab

Corrigé:

1) La dérivation la plus à gauche : 2)

1) La dérivation la plus à gauche : 2)

bS, S fi

abSb}

S ⇒ abSbS

⇒ ababS

⇒ ababaAb

⇒ abababSb

⇒ abababab

(3)

(2)

(1)

(4)

(2)

a

b

S

S

a

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

b

S

a A b

b

S

a

38

IV.5. Dérivation, arbre et ambiguïté

3) S ⇒ aAb ⇒ abSb ⇒ abab

S ⇒ abSb ⇒ abab

a

a

b

A

A

A

b

b

S

b

S

a

a

b

b

b

b

S

S

a

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

39

IV.5. Dérivation, arbre et ambiguïté

Ambiguïté

Une grammaire G est dite ambiguë s’il existe un mot de L(G) qui a au moins 2

dérivation lpg à partir de S (donc deux arbres différents sont associés à ce mot).

Sinon G est non – ambiguë.

Exercice : Montrer que la grammaire G

Exercice : Montrer que la grammaire G

suivante est ambigüe:

G = ({S, A}, {a, b}, b, R)

R = { S fi

aAb, S fi

a, S fi

abSb, A fi

bS}

Corrigé:

en effet, pour le mot abab il y a deux

dérivations lpg

S ⇒ aAb ⇒ abSb ⇒ abab

S ⇒ abSb ⇒ abab

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

40

IV.6. Propriétés des langages non contextuels

(LNC)

Soit LNC, l’ensemble des langages non contextuels:

-Si L1 ˛

LNC alors

-L1 ¨

-L1.L2 ˛

-L1.L2 ˛

LNC et L2 ˛

L2 ˛

LNC

-Si L ˛

LNC, L+ ˛

-On n’a pas la propriété pour L1˙

LNC et L ˛

˙ L2 et pour L

LNC

LNC

LNC

LNC alors L* ˛

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

41

˛

˛

˛

˛

˛

˛

¨

¨

¨

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˛

˙

˙

IV.6. Propriétés des langages non contextuels

(LNC)

-Si L1 ˛

L1 ¨

LNC et L2 ˛

L2 ˛

LNC

LNC alors

En effet, on peut construire une grammaire non contextuelle

qui génère L1 ¨

L2 à partir des grammaires non contextuelles

qui génèrent L1 et L2

qui génèrent L1 et L2

Soit G1 = (V1, T1, S1, R1) / L(G1) = L1 et

G2 = (V2, T2, S2, R2)/ L(G2) = L2

On peut construire G = (V, T, S, R) / L(G) = L(G1)¨

L(G2)

• V= V1¨ V2 ¨

{S} où S n’apparaît ni dans V1 ni dans V2

et V1 et V2 sont disjoints si non on doit renommer les

non terminaux

• T = T1¨
• R = R1 ¨ R2 ¨

S1, S fi

S2}

{S fi

T2

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

42

˛

˛

˛

˛

˛

˛

¨

¨

¨

˛

˛

˛

fi

fi

fi

fi

fi

fi

IV.6. Propriétés des langages non contextuels

(LNC)

Exercice : Soient les langages L1 et L2 générés respectivement par G1 et

G2.

L1 = {anbn / n‡ 0}

L2 = {a2nbn / n ‡ 0}

G1 = ({S1}, {a, b}, S1, {S1fi

G2 = ({S2}, {a, b}, S2, {S2fi

G2 = ({S2}, {a, b}, S2, {S2fi

| aS1b})

| aaS2b})

| aaS2b})

1) Construire une grammaire G / L(G) = L1 ¨

2) Vérifier que le mot aab est généré par la grammaire G

L2

Corrigé :

1) G = ({S1, S2, S}, {a, b}, S, {Sfi

S2fi

aaS2b})

S1, Sfi

S2, S1fi

, S1fi

aS1b, S2fi

,

2) Le mot aab est généré par G en effet S ⇒* aab

S ⇒ S2 ⇒ aaS2b ⇒ aab donc aab ˛

L(G)

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

43

e

e

e

¨

¨

¨

e

e

IV.6. Propriétés des langages non contextuels

(LNC)

-Si L1 ˛

LNC et L2 ˛

LNC

L1 .L2 ˛

LNC alors

En effet, on peut construire une grammaire non contextuelle

qui génère L1.L2 à partir des grammaires non contextuelles

qui génèrent L1 et L2

qui génèrent L1 et L2

Soit G1 = (V1, T1, S1, R1) / L(G1) = L1 et

G2 = (V2, T2, S2, R2)/ L(G2) = L2

On peut construire G = (V, T, S, R) / L(G) = L(G1).L(G2)

• V= V1¨ V2 ¨

{S} où S n’apparaît ni dans V1 ni dans V2

et V1 et V2 sont disjoints si non on doit renommer les

non terminaux

• T = T1¨
• R = R1 ¨ R2 ¨

{S fi

T2

S1 S2}

Théorie des Langages et Compilation - 2013

Leila Jemni Ben Ayed

44

˛

˛

˛

˛

˛

˛

˛

˛

˛

fi

fi

fi

IV.6. Propriétés des langages non contextuels

(LNC)

Exercice: Construire une grammaire qui génère L1.L2

L1 = l+

L2 = (l+c)+ où

l ˛ {a, b, c, …z, A, B, C, …Z}= L et

c ˛

G1 = ({S1}, L, S1, R1)

G2 = ({S2}, L¨ C, S2, R2)

G2 = ({S2}, L¨ C, S2, R2)

{0, 1, 2, 3, …, 9}= C

R1 = {

S1 fi

S1 fi

S1 fi

S1 fi

a,

fi A, S1 fi

fi b,…. S1 fi

S1 fi

fi B, … S1 fi

aS1, S1 fi

fi AS1, S1 fi

Z,

fi bS1,…. S1 fi

fi BS1, … S1 fi

zS1,

ZS1}

z ,

R2 = {

z ,

S2 fi

S2 fi

S2 fi

S2 fi

S2 fi

S2 fi

fi b,…. S2 fi

a,

fi A, S2 fi

fi 0,

S2 fi

fi B, … S2 fi

S2 fi

aS2, S2 fi

fi AS2, S2 fi

fi 0S2, S2 fi

Z,

fi 9,

fi 1,…. S2 fi

fi bS2,…. S1 fi

fi BS2, … S2 fi

fi 1S2, … S2 fi

zS2,

ZS2,

fi 9S2}

Corrigé: G / L(G) = L1.L2 = l+(l+c)+

{Sfi

G = ({S1,S2,S}, L¨ C, S, R1¨ R2 ¨

S1S2})

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

45

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

IV.6. Propriétés des langages non contextuels

(LNC)

Exercice :

1) Construire une grammaire G qui génère L1. L2

2) Vérifier que le mot temp1 est généré par G

L1 = l+

L2 = (l+c)* où

l ˛ {a, b, c, …z, A, B, C, …Z}= L et

c ˛

G1 = ({S1}, L, S1, R1)

G1 = ({S1}, L, S1, R1)

G2 = ({S2}, L¨ C, S2, R2)

S1 fi

z ,

a,

fi B, … S1 fi

fi A, S1 fi

{0, 1, 2, 3, …, 9}= C

fi b,…. S1 fi

R2 = {

R1 = {

S1 fi

S1 fi

S1 fi

S1 fi

aS1, S1 fi

fi AS1, S1 fi

Z,

fi bS1,…. S1 fi

fi BS1, … S1 fi

zS1,

ZS1}

S2 fi

S2 fi

S2 fi

S2 fi

aS2, S2 fi

fi AS2, S2 fi

fi 0S2, S2 fi

fi bS2,…. S1 fi

fi BS2, … S2 fi

fi 1S2, … S2 fi

zS2,

ZS2,

fi 9S2}

Corrigé :

1) G / L(G) = L1.L2 = l+(l+c)*

G = ({S1,S2,S}, L¨ C, S, R1¨ R2 ¨

{Sfi

S1S2})

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

46

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

e

fi

e

fi

e

fi

e

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

fi

IV.6. Propriétés des langages non contextuels

(LNC)

G / L(G) = L1.L2 = l+(l+c)*

G = ({S1,S2,S}, L¨ C, S, R1¨ R2 ¨

{Sfi

S1S2})

2) Vérifier que le mot temp1 est généré par G

2) Vérifier que le mot temp1 est généré par G

Mq S ⇒* temp1

S ⇒ S1S2 ⇒ tS1S2 ⇒teS1S2 ⇒temS1S2 ⇒tempS2 ⇒temp1S2

⇒temp1

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

47

IV.6. Propriétés des langages non contextuels

(LNC)

LNC

LNC alors L* ˛

-Si L ˛

En effet, on peut construire une grammaire non contextuelle

qui génère L* à partir d’une grammaire non contextuelles qui

génère L

Soit G1 = (V1, T1, S1, R1) / L(G1) = L

Soit G1 = (V1, T1, S1, R1) / L(G1) = L

On peut construire G = (V, T, S, R) / L(G) = (L(G1))*

• V= V1¨
• T = T1
• R = R1 ¨

{S} où S n’apparaît pas dans V1

{S fi

e , S fi

S1 S}

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

48

˛

˛

˛

˛

˛

˛

fi

fi

fi

e

e

e

fi

fi

fi

IV.6. Propriétés des langages non contextuels

(LNC)

Exercice : Soit la grammaire G1 suivante qui génère le

langage L = {a, b}

G1 = ({S1}, {a, b}, S1, {S1fi

a |b})

1) Construire une grammaire G / L(G) = L*

2) Vérifier que le motaab est généré par la grammaire G

2) Vérifier que le motaab est généré par la grammaire G

Corrigé :

1) G = ({S1, S}, {a, b}, S, {S fi

S1fi

a, S1fi b})

e , S fi

S1 S,

2) Vérifier que le mot aab est généré par G. Mq S ⇒* aab

S ⇒ S1S ⇒ S1S1S ⇒ S1S1S1S ⇒ aS1S1S ⇒ aaS1S ⇒ aabS ⇒ aab

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

49

fi

fi

fi

e

e

e

fi

fi

fi

IV.6. Propriétés des langages non contextuels

(LNC)

-On n’a pas Si L1 ˛

Contre exemple:

LNC et L2 ˛

LNC alors L1 ˙

˙ L2 ˛

LNC

L1 = {aibick/ i ‡ 0, k‡ 0} ˛

G1 = ({S, S1, S2}, {a, b, c}, S, {Sfi

LNC

L2 = {akbici/ i ‡ 0, k‡ 0} ˛

G2 = ({A, B, C}, {a, b, c}, C, {Cfi AB, A fi

L1 ˙

L2 = {aibici/ i ‡ 0} ˇ

LIC

e |aS1b,

S1 S2, S1 fi

S2 fi

S2 fi

LNC

e |cS2})

e |cS2})

e |aA,

e |bBc})

B fi

car il n’existe aucune

grammaire non

contextuelle qui le

génère

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

50

˛

˛

˛

˛

˛

˛

˙

˙

˛

˛

˛

e

e

e

e

e

e

e

e

e

e

e

e

e

e

e

V. Les automates à Piles

Plan

Présentation

V.1.

V.2. Définition d’un automate à pile

V.3. Description d’un automate à pile

V.3. Description d’un automate à pile

Exemple d’automate à Pile

V.4.

Fonctionnement d’un automate à pile

V.5.

Langages acceptés par des automates à pile

V.6.

Construction d’un automate à pile à partir

V.7.

d’une grammaire non contextuelle

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

51

V.1. Présentation

L’automate fini permet de représenter une grammaire régulière. Par suite, il permet de

reconnaître des mots d’un langage régulier (associé à une grammaire régulière).

À une règle (A fi

d (A, x, B)

x B) d’une grammaire régulière, on peut associer une transition

A

A

x

x

B

B

Partant d’une grammaire non contextuelle ayant une règle de production de la forme

(A fi

x B y), l’automate doit se souvenir qu’il doit lire la chaine y après avoir lu la sous

chaine dérivant de B. Pour cette raison, on ajoute une pile à l’automate fini où on

empile ce que nous avons à lire (y) et après avoir dérivé la sous chaine dérivant de B,

on doit lire y et dépiler le y de la pile.

On parle d’automate à pile

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

52

fi

fi

fi

fi

fi

fi

V.2. Définition d’un automate à pile

Un automate à pile A est un septuplet

A = < X, Q, q0, F, G

, Z0, d

d >

Où

X est un alphabet

Q est un ensemble d’états

˛ Q est l’état initial

q0

F ˝ Q est l’ensemble des états finaux

G est le vocabulaire de la pile

Z0 est le symbole initial de la pile (symbole de fond de pile)

d est une fonction de transition

{e }) x G

{ parties finies de Q x G *}

: Q x (X ¨

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

53

G

G

G

d

d

G

G

G

d

fi

V.3. Description d’un automate à pile

Z0

Pile

Tête de lecture/écriture

q

Unité de contrôle

Tête de lecture

U

V

Ruban d’entrée

L’unité de contrôle, se trouve à un état q munie de deux têtes (L/E sur pile

et L sur ruban d’entrée). Le ruban d’entrée sert de support à un mot de X*.

La lecture se fait de gauche à droite. La pile est un ruban infini du côté droit

où sont lus et écrits les symboles de la pile (˛

celle qui contient le symbole le plus à droite.

*). La case lue est toujours

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

54

G

V.4. Exemple d’un automate à pile qui

accepte {ancbn / n‡ 0}

(a, Z0, Z0a)

(a, a, aa)

q0

(c, a, a)

(c, Z0 , Z0)

(c, Z , Z )

q1

(b, a, e )

e )

e , Z0, e

(e

•Commencer par empiler tous les a

•On doit lire un c

•Le c peut être précédé d’un a

comme il peut être le seule

symbole dans le mot

•Dans les deux cas, il ne doit pas

•Dans les deux cas, il ne doit pas

être empilé et il faut changer

d’état pour séparer la lecture

des a de la lecture des b.

•si on lit un b alors il doit être

précédé d’un a. On le dépile et on

continue à accepter uniquement des

b et dépiler les a correspondants.

•A la fin, il faut arriver à vider la pile

Leila Jemni Ben Ayed

Théorie des Langages et Compilation - 2013

55

e

e

e

e

Exemple d’un automate à pile qui

accepte {ancbn / n‡ 0} suite

Acceptation du mot aacbb

a a c b b

a a c b b

a a c b b

a a c b b

a a c b b

a a c b b

a a c b b

q0

q0

q0

q1

q1

q1

q1

Z0

Z0a

Z0aa

Z0aa

Z0a

Z0

Le mot aacbb est lu et la pile est vide alors il est acce...