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°3

Exercice 1

Soit le langage L = {a, b}*.{a, b, c}*.{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²ⁿ / n ≥ 0} ;

b) {aⁿb^m / n, m ≥ 1} ;

c) {aⁿbⁿ / n ≥ 0} ;

d) {ww^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) Écrire le système d’équations associé.

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

FAQ

Qu’est-ce qu’une dérivée d’un langage ?

La dérivée d’un langage L par rapport à un mot w (notée L_w) est l’ensemble des suffixes des mots de L qui commencent par w.

Comment vérifier si un langage est régulier à l’aide des dérivées ?

Un langage L est régulier si et seulement si pour tout mot w, l’ensemble des dérivées L_w est fini. Cette méthode consiste à calculer les dérivées successives et à vérifier leur finitude.

Qu’est-ce qu’un automate d’états finis simple ?

Un automate simple est un automate déterministe (ou non) où chaque état est soit un état final, soit un état non final, sans structure interne supplémentaire (comme des piles). Il est utilisé pour décrire des langages réguliers.