Introduction aux grammaires

• toute règle est de la forme : #A$ " #%$, avec

% # (V " T)+ et #,$ # (V " T)*

• on peut avoir la règle S " &, si S n’apparaît

dans aucun membre de droite

• reconnue par une machine de Turing non-déterministe à

ruban de longueur bornée par un multiple fixé de la longueur

du mot d'entrée.

Hiérarchie de Chomsky

Hiérarchie de Chomsky

• Classe 2: Grammaires context-free

• toute règle est de la forme : A " #

• reconnue par un automate à pile non

déterministe

• Classe 3: grammaires régulières (2 types)

• grammaire linéaires droites règles du type :

A " wB ou A " w

• grammaires linéaires gauches règles du

type : A " Bw ou A " w

• reconnue par un automate fini

Exemples

G’: grammaire

context-free

1. S " aSb

2. S " &

Classe 1

n n n

0 1 2

Classe 2

n n

0 1

Classe 3

(0+1)*

G: grammaire

context-sensitive

1. S " ABS

2. BA " AB

3. BS " b

4. Bb " bb

5. Ab " ab

6. Aa " aa

L(G) = L(G’) = {anbn}

L(G) est un langage context-free (et donc aussi context-

sensitive) bien que ça grammaire ne l’est pas

Exercice 1

Décrivez, en français, les langages générés par les

grammaires suivantes, et donnez leur type:

1. S " abcA

" Aabc

A " &

Aa " Sa

cA " cS

2. S " 0

" 1

" 1S

3. S " a

" *SS

" +SS

Solution 1

1. Grammaire non restreinte donnant toutes les

suites de abc.

2. Grammaire linéaire droite donnant toutes les

suites de 1 éventuellement terminées par un 0,

ou bien le string 0.

3. Grammaire context-free donnant toutes les

expressions arithmétiques utilisant la somme et

le produit sur la variable a, et ce, en notation

polonaise.

Exercice 2

Soit la grammaire G suivante :

S " AB

A " Aa

bB

B " a

Sb

Cette grammaire est-elle régulière ?

Donnez l’arbre de dérivation pour baabaab, bBABb et baSb

Donnez les dérivations gauche et droite de baabaab.

Solution 2

Il s’agit d’une grammaire context-free mais pas

régulière. Justification : il ne peut pas y avoir à la

fois une règle de la forme A " #B et une règle de

la forme A " B$ dans une grammaire régulière.

Solution 2

S

A

B

b

B

S

b

A

B

Solution 2

A

b

A

B

a

S

a

S

A

b

B

a

b

B

B

a

Solution 2

S

A

B

S

b

b

B

a

Solution 2

Exercice 3

1. La dérivation gauche de baabaab est : S $

AB $ AaB $ bBaB $ baaB $ baaSb $

baaABb $ baabBBb $ baabaBb $ baabaab

2. La dérivation droite est : S $ AB $ ASb $

AABb $ AAab $ AbBab $ Abaab $

Aabaab $ bBabaab $ baabaab

Solution 3

S " bSa|aSb|abS|baS|Sab|Sba|Sa|aS|a

On dérive baaba de la façon suivante :

S $ baS $ baabS $ baaba

1. Écrivez une grammaire context-free qui génère

toutes les chaînes de a et de b (dans n’importe quel

ordre), tel qu’il y a plus de a que de b. Testez votre

grammaire sur baaba en en donnant une dérivation.

2. Écrivez une grammaire context-sensitive qui

génère toutes les chaînes de a, de b et de c (quel

que soit l’ordre), ayant le même nombre de a, de b

et de c. Donnez la dérivation de cacbab selon votre

grammaire.

Solution 3

S " ABCS | &

AB " BA

AC " CA

BA " AB

BC " CB

CA " AC

CB " BC

A " a

B " b

C " c

S $ ABCS $ ABCABCS $ ABCABC $

ACBABC $ CABABC $ CABACB $ CABCAB

$ CACBAB $ cACBAB $ caCBAB $ cacBAB

$ cacbAB $ cacbaB $ cacbab

Exercice 4

1. Écrivez une grammaire context-free pour les

langages 0i1n2n et 0n1n2i, avec n,i > 0

2. Montrer que soient L1 et L2 deux langages context-

free, L1 ' L2 n’est pas nécessairement context-free.

Solution 4

S " AB

S " AB

A " 0A | 0

A " 0A1 | 01

B " 1B2 | 12

B " 2B | 2

1. Les langages L1 = {0i1n2n | n > 0, i > 0} et L2 =

{0n1n2i | n > 0, i > 0} sont context-free, alors que

L1 ' L 2 = {0n1n2n | n > 0} ne l’est pas

2. Soient L1 = % et L2 = {0n1n | n > 0} deux langages

context-free, on a L1 ' L 2 = % qui est context-free