TD Automates, langages et applications

–

2. Soit L0 l’ensemble des mots de longueur non nulle contenant autant de a que de b, La l’ensemble

des mots ayant un a de plus que de b et Lb l’ensemble des mots ayant un b de plus que de a.

Nous allons montrer que







(S ∗⇒ w) ⇐⇒ w ∈ L0

(A ∗⇒ w) ⇐⇒ w ∈ La

(B ∗⇒ w) ⇐⇒ w ∈ Lb.

Si |w| = 1, (w ∈ La) ⇐⇒ (w = a) ⇐⇒ (A ∗⇒ a) et (w ∈ Lb) ⇐⇒ (w = b) ⇐⇒ (B ∗⇒ b).

Si |w| = 2, si w ∈ L0 alors w = ab et S ⇒ aB ⇒ ab ou bien w = ba et S ⇒ bA ⇒ ba ; de même

si S ∗⇒ w, on a forcément w = ab ou w = ba et donc w ∈ L0.

Supposons maintenant S ∗⇒ w. La dérivation commence soit par S ⇒ aB ∗⇒ w, soit par S ⇒

bA ∗⇒ w. Dans le premier cas, on a B ∗⇒ w(cid:48) avec |w(cid:48)| < |w| et donc w(cid:48) ∈ Lb ce qui donne

aw(cid:48) = w ∈ L0 ; dans le deuxième cas, on a A ∗⇒ w(cid:48) avec |w(cid:48)| < |w| et donc w(cid:48) ∈ La ce qui donne

bw(cid:48) = w ∈ L0. Les cas A ∗⇒ w et B ∗⇒ w se traitent de la même manière.

Dans l’autre sens, supposons w ∈ L0. w est de longueur non nulle, il s’écrit donc w = aw(cid:48) (resp.

w = bw(cid:48)). Dans le premier cas, w(cid:48) ∈ Lb (resp. La) et donc B ∗⇒ w(cid:48) (resp. A ∗⇒ w(cid:48)). On a alors

une dérivation S ⇒ aB ∗⇒ aw(cid:48) = w (resp. S ⇒ bA ∗⇒ bw(cid:48) = w). Les cas w ∈ La et w ∈ Lb se

traitent pareillement.

Exercice 4 Quel est le langage reconnu par la grammaire :

S → AB | C

A → aAb | ab

B → cBd | cd

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

(cid:127)

(cid:15)

(cid:15)

(cid:127)

(cid:15)

(cid:15)

(cid:39)

(cid:127)

(cid:15)

(cid:15)

(cid:32)

(cid:15)

(cid:15)

(cid:32)

(cid:39)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:32)

(cid:126)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

4

Exercices Corrigés TD 6

TD Automates, langages et applications

C → aCd | aDd

D → bDc | bc

Corrigé : Si on part avec la regle S → AB, on génere d’abord autant de a que de b, puis autant de

c que de d ; le langage est donc {anbncmdm}.

Si on part avec la regle S → C, on génere d’abord autant de a que de d, puis autant de b que de

c ; le langage est donc {anbmcmdn}.

Finalement, le langage reconnu est {anbncmdm} ∪ {anbmcmdn} pour n,m ≥ 1.

Exercice 5 Montrer que la grammaire

génere tous les mots de parentheses équilibrés et (cid:40)(cid:40) corrects (cid:41)(cid:41).

S → (S)S | ε

Corrigé :

1. Montrons tout d’abord que tous les mots générés sont équilibrés et corrects (abrévié en corrects).

Il suffit de faire une récurrence sur la longueur de la dérivation a gauche qui aboutit a un mot.

– Au rang 1, S ⇒ ε, qui est correct.

– Soit une dérivation à gauche de n étapes S ⇒ (S)S ∗⇒ (x)S ∗⇒ (x)y. x et y dérivent de S

en moins de n étapes, donc ils sont corrects et (x)y l’est également.

2. Montrons maintenant que tous les mots corrects sont générés. Nous allons faire une récurrence

sur la longueur du mot.

– Le seul mot correct de longueur 0 est ε et il est généré.

– Supposons que tous les mots corrects de longueur inférieure à 2n sont générés. Soit un

mot de longueur 2n correct. Il commence forcément par (. Soit (x) son plus petit préfixe

ayant autant de ( que de ). Le mot s’écrit alors (x)y où x et y sont corrects et de longueur

inférieure à 2n. Donc ils sont tous les deux générés. Autrement dit, S ∗⇒ x et S ∗⇒ y. Mais

alors : S ⇒ (S)S ∗⇒ (x)S ∗⇒ (x)y.

2 Grammaires ambiguës

Exercice 6

S → aSbS | bSaS | ε

Montrer que cette grammaire est ambiguë en générant deux dérivations à gauche pour abab. Donner

deux dérivations à droite de abab. Quels sont les arbres de dérivation correspondants?

Corrigé : Les dérivations à gauche sont : S ⇒ aSbS ⇒ abS ⇒ abaSbS ⇒ ababS ⇒ abab

et S ⇒ aSbS ⇒ abSaSbS ⇒ abaSbS ⇒ ababS ⇒ abab.

Les dérivations à droite sont : S ⇒ aSbS ⇒ aSbaSbS ⇒ aSbaSb ⇒ aSbab ⇒ abab

et S ⇒ aSbS ⇒ aSb ⇒ abSaSb ⇒ abSab ⇒ abab.

Les arbres sont :

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

TD Automates, langages et applications

Exercices Corrigés TD 6

5

(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)

a

S

S

ε

(cid:39)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)

(cid:30)(cid:62)(cid:62)(cid:62)(cid:62)

(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)

b

a

(cid:39)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)(cid:78)

(cid:30)(cid:61)(cid:61)(cid:61)(cid:61)

b

S

S

ε

b

S

ε

(cid:119)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)(cid:111)

(cid:127)(cid:127)(cid:127)(cid:127)

(cid:119)(cid:112)(cid:112)(cid:112)(cid:112)(cid:112)(cid:112)(cid:112)(cid:112)(cid:112)

(cid:31)(cid:63)(cid:63)(cid:63)

(cid:127)(cid:127)(cid:127)(cid:127)

S

a

a

S

ε

(cid:31)(cid:63)(cid:63)(cid:63)

S

ε

S

b

S

ε

Exercice 7 Soit la grammaire

R → R(cid:48)|(cid:48)R | RR | R∗ | (R) | a | b

1. Montrer que cette grammaire génere les expressions régulieres sur l’alphabet {a, b}.

2. Montrer que cette grammaire est ambiguë.

3. Construire une grammaire équivalente non-ambiguë avec les priorités classiques (∗ puis . puis |)

et l’associativité à gauche.

4. Construire un arbre de dérivation pour a|b*b dans les deux grammaires.

Corrigé :

– Elle est ambiguë car, par exemple, on a a|b∗ qui peut être généré de deux façons par une dérivation

à gauche : R ⇒ R|R ⇒ a|R ⇒ a|R∗ ⇒ a|b∗ et R ⇒ R∗ ⇒ R|R∗ ⇒ a|R∗ ⇒ a|b∗.

–

R → R(cid:48)|(cid:48)T | T

T → T F | F

F → F ∗ | a | b | (R)

(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)

R

T

F

a

(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)

(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)

(cid:32)(cid:64)(cid:64)(cid:64)(cid:64)

T

F

b

∗

R

|

T

F

F

b

(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)

R

a

(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)

(cid:127)(cid:0)(cid:0)(cid:0)(cid:0)

(cid:31)(cid:64)(cid:64)(cid:64)(cid:64)

R

|

R

R

b

R

(cid:31)(cid:62)(cid:62)(cid:62)(cid:62)

∗

R

b

Exercice 8 Reprenons la grammaire de l’exercice 4 :

S → AB | C

A → aAb | ab

B → cBd | cd

C → aCd | aDd

D → bDc | bc

Montrer que cette grammaire est ambiguë.

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

(cid:0)

(cid:15)

(cid:15)

(cid:30)

(cid:39)

(cid:119)

(cid:127)

(cid:15)

(cid:15)

(cid:31)

(cid:15)

(cid:15)

(cid:0)

(cid:15)

(cid:15)

(cid:30)

(cid:39)

(cid:119)

(cid:127)

(cid:15)

(cid:15)

(cid:31)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:127)

(cid:15)

(cid:15)

(cid:31)

(cid:127)

(cid:15)

(cid:15)

(cid:31)

(cid:15)

(cid:15)

(cid:127)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:127)

(cid:31)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:31)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

(cid:32)

(cid:15)

(cid:15)

(cid:15)

(cid:15)

6

Exercices Corrigés TD 6

TD Automates, langages et applications

Corrigé : Le langage lui-même est (cid:40)(cid:40) ambigu (cid:41)(cid:41) : si n = m, les mots anbncmdm et anbmcmdn sont

identiques.

Ainsi, on a les deux dérivations suivantes :

S → AB → abB → abcd

S → C → aDd → abcd

Exercice 9 On considère la grammaire suivant :

S → aS | bS | bA

A → bA | b

1. Montrer que cette grammaire est ambiguë en produisant tous les arbres de dérivation que l’on

peut obtenir pour le mot aabbbb.

2. Un moyen que nous pourrions utiliser (non vu en cours) pour désambigu¨ıser une grammaire

consiste a assigner des probabilités aux regles de production de la grammaire de telle manière

que

(cid:88)

p(A → α) = 1

α∈(V ∪T )+

avec (A → α) ∈ P .

On peut alors déterminer la probabilité d’une dérivation en calculant le produit des probabilités

assignées aux règles de production utilisées pendant la dérivation. On peut par exemple attribuer

les probabilités suivantes aux règles de production de notre grammaire :

S → aS (0,8) | bS (0,01) | bA (0,19)

A → bA (0,9) | b (0,1)

Parmi les dérivations obtenues à la question précédente, déterminer celle qui est désormais la

plus probable.

Corrigé :

1. On a les trois dérivations suivantes :

S → aS → aaS → aabS → aabbS → aabbbA → aabbbb

S → aS → aaS → aabS → aabbA → aabbbA → aabbbb

S → aS → aaS → aabA → aabbA → aabbbA → aabbbb

2. Ce qui nous donne les probabilités suivantes :

S

S

0,8

→ aS

0,8

→ aS

0,8

→ aS

0,8

→ aaS

0,8

→ aaS

0,8

→ aaS

0,01

→ aabS

0,01

→ aabS

0,19

→ aabA

0,01

→ aabbS

0,19

→ aabbA

0,9

→ aabbA

0,19

→ aabbbA

0,9

→ aabbbA

0,9

→ aabbbA

S

0,1

→ aabbbb

0,1

→ aabbbb

0,1

→ aabbbb

C’est clairement la dernière dérivation qui est la plus probable.

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

TD Automates, langages et applications

Exercices Corrigés TD 6

7

3 Simplification de grammaires

Exercice 10 Supprimer (en expliquant la procédure) les symboles inutiles de la grammaire :

S → aAAB | CC | cA

A → aA | a

C → cC

Corrigé : A la premiere étape, on garde A qui dérive un terminal (a) puis S qui dérive une phrase

formée d’un terminal et d’une variable déjà conservée (cA). Cela nous donne la grammaire :

S → cA

A → aA | a

La deuxième étape ne permet pas d’éliminer d’autres symboles car A dérive de S. La grammaire

ci-dessus est donc une grammaire équivalente sans symboles inutiles.

Exercice 11 Supprimer (en expliquant la procédure) les ε-productions de la grammaire :

S → AB

A → aA | ε

B → b | ε

Corrigé : A et B sont annulables et donc S également. On obtient donc la grammaire:

S → AB | A | B

A → aA | a

B → b

On peut rajouter la règle S → ε si on veut garder la possibilité de générer ε.

Exercice 12 Supprimer (en expliquant la procédure) les règles unitaires de la grammaire :

S → ABc

A → B

B → B | b | c

Corrigé : Les règles S → ABc et B → b|c sont non-unitaires, il faut les garder. Comme A ∗⇒ B et

qu’on a la regle non-unitaire B → b|c, il faut rajouter la regle A → b|c. On obtient :

S → ABc

A → b | c

B → b | c

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

8

Exercices Corrigés TD 6

TD Automates, langages et applications

Exercice 13 Transformer la grammaire suivante en une grammaire équivalente (sans ε) sans sym-

boles inutiles, sans ε-productions et sans règles unitaires.

S → AB | CA

A → a | b | ε

B → BC | DB

C → E | ε

D → a | d

E → aB | c | d | ε

Corrigé :

1. Éliminons d’abord les symboles inutiles. A la premiere étape, seul B ne permet pas de dériver un

terminal ou une phrase composée de terminaux et de variables dérivant une phrase terminale.

On peut donc l’éliminer. On obtient donc :

S → CA

A → a | b | ε

C → E | ε

D → a | d

E → c | d | ε

Pour la deuxième étape, S dérive CA et C dérive E, il faut donc garder A, C, E et S comme

variables. Voici notre grammaire sans symboles inutiles :

S → CA

A → a | b | ε

C → E | ε

E → c | d | ε

2. A, C, E et S sont annulables, on obtient donc une grammaire équivalente (ne générant pas ε),

sans ε-productions :

S → CA | C | A

A → a | b

C → E

E → c | d

3. Nous avons trois règles unitaires : S → C, S → A et C → E. Par ailleurs on peut dériver S ∗⇒ A,

S ∗⇒ C, S ∗⇒ E et C ∗⇒ E, donc on obtient la grammaire sans règles unitaires :

S → CA | a | b | c | d

A → a | b

C → c | d

E → c | d

4. On termine en éliminant à nouveau les symboles devenus inutiles : E ne dérive pas de S, donc

on obtient la grammaire suivante.

S → CA | a | b | c | d

A → a | b

C → c | d

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

TD Automates, langages et applications

Exercices Corrigés TD 6

9

Exercice 14 On considere la (célebre) grammaire des expressions arithmétiques bien formées, où n

désignera par commodité tout entier positif (traité ici comme un terminal).

S → T + S | S + T | T

T → F ∗ T | T ∗ F | F

F → n | (S)

Mettre cette grammaire sous forme normale de Chomsky.

Utiliser l’algorithme CYK (Cocke, Younger et Kasami) pour déterminer si le mot n+(n) est généré

par cette grammaire.

Corrigé : Pour mettre sous forme normale de Chomsky, on procede d’abord a l’élimination des

(cid:15)-transitions, des productions unités et des symboles inutiles.

La grammaire ne comporte pas de (cid:15)-transitions. L’élimination des productions unités nous donne

la grammaire :

S → T + S | S + T | F ∗ T | T ∗ F | n | (S)

T → F ∗ T | T ∗ F | n | (S)

F → n | (S)

La grammaire ne comporte pas de symboles inutiles.

Pour la mise sous forme normale de Chomsky, on introduit d’abord de nouvelles variables pour tous

les symboles terminaux qui apparaissent dans les parties droites des règles de longueur plus grande

que 2.

S → T O1S | SO1T | F O2T | T O2F | n | P1SP2

T → F O2T | T O2F | n | P1SP2

S → n | P1SP2

O1 → +

O2 → ∗

P1 → (

P2 → )

Puis on scinde de maniere a obtenir des règles avec deux symboles, en introduisant de nouveaux

symboles (Xi)

S → T X1 | SX2 | F X3 | T X4 | n | P1X5

T → F X3 | T X4 | n | P1X5

F → n | P1X5

O1 → +

O2 → ∗

P1 → (

P2 → )

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard

10

Exercices Corrigés TD 6

TD Automates, langages et applications

X1 → O1S

X2 → O1T

X3 → O2T

X4 → O2F

X5 → SP2

On applique ensuite l’algo CYK, et on obtient le tableau suivant:

{S}

∅

∅

∅

{S, T, F } O1

+

n

{X1, X2}

∅

∅

{S, T, F }

∅

P1

(

{X5}

{S, T, F } P2

n

)

Donc le mot est bien généré par cette grammaire.

Université Paris-Dauphine

M1 Master MIAGE&D - 2009/2010

B, Escoffier, E. Lazard