Exercices série d exercices n 3 Théorie des langages

Théorie des langages : Exercices série d exercices n 3

Télécharger PDF

Année universitaire : 2017/2018 Faculté de génie électrique et informatique

2ième année Licence-Informatique Département d’informatique

module : Théorie des langages SÉRIE D’EXERCICES n

o 3

Exercice

Soit le langage L = {a, b}.{a, b, c}

2 {c}.{a, b}.

a) Trouver

toutes les dérivées de L par rapport aux mots w ∈ {a, b, c}* .

b) L est-il régulier ?

c) Construire l’automate d’états finis qui accepte L.

Exercice 2

Utiliser les dérivées pour vérifier si les langages suivants sont réguliers :

a) { a

2.n / n ≥ 0 } ;

c) { an .b

n / n ≥ 0 } ;

b) { an .bm / n, m ≥ 1 } ;

d) { w.w

R / w ∈ {a, b}

* }.

Exercice 3

I) Trouver, intuitivement, des automates qui acceptent les langages dénotés par les

expressions régulières :

I-1) (a b c)* .a.b.c.(a b c)

* ;

I-2) aa.(a b)* (ab)* .bb.

II) En utilisant les dérivées, construire des automates correspondants aux expressions régulières :

II-1) (1.1* .0.0* .1)* .0.1

* ;

II-2) (a ba)* .bb.b* .a.

Exercice 4

Soient A et B deux langages quelconques liés par l’équation : X = A.X  B.

1) Montrer que A* .B est la solution minimale de l’équation.

2) Montrer que si ε ∉ A, alors cette solution est unique.

Exercice 5

Soit la grammaire g = {a, b, c}, {S, A, B}, S, où :

P = { S → aA | ε ; A → bA | cB ; B → bB | a }

1) Trouver le système d’équations (d’expressions régulières) correspondant.

2) Résoudre ce système.

Exercice 6

Soit la grammaire g = ;{a, b, c}, {S, A, B}, S, P; où :

P = { S → baA | aS | ε ; A → aA | bB | ε ; B → cB | aA }

a) Construire l’automate d’états finis simple équivalent à g.

b) Ecrire le système d’équations associé

c) Trouver l’expression régulière qui dénote