Td 1 langages réguliers et expressions régulières Théor...

Théorie des langages : Td 1 langages réguliers et expressions régulières

Télécharger PDF

Université Sidi Mohamed Ben Abdellah
École Nationale des Sciences Appliquées
Année Universitaire : 2019-2020
Module : Théorie des langages
Filière : GINF - 1ère Année
Professeur : [Nom non mentionné]

Correction - TD 1 : Notions fondamentales de la théorie des langages / Langages réguliers et expressions régulières

Exercice 1

1) L = { a²bⁿ | n ≥ 0 } ou L = { (aa)ⁿbⁿ | n ≥ 0 }

2) L = { w_n · (w + ε) · w_n | w ∈ Σ, n ≥ 0 } ou L = { wⁿ | w ∈ Σ, n ≥ 0 }

3) L = { u · (w + ε) · u^R | w ∈ Σ, u ∈ Σ* }

Exercice 2

– ε n'appartient à aucun langage

– a appartient à L₂, L₃ et L₅

– abba appartient à L₂

– abbaaac appartient à L₄

– aba appartient à L₂ et L₃

– aabba appartient à L₁, L₂, L₆ et L₇

– abb appartient à L₂, L₃ et L₅

Exercice 3

– L₂ · L₃ = { ab, aba, aab, aaba, b, ba }

– L₂ · L₁ = L₁

– L₁ · L₃ = { aⁱb^j · (a + ε) | i ≥ j − 1 ≥ 1 }

– L₅ ∩ L₁ = L₆

– L₆ ∪ L₅ = L₅

– L₁ · (L₂ ∩ L₄) = L₁

– L₁ · (L₂ ∩ L₃) = ∅

– (L₁ · L₂)^R = { (ε + a + aa) · b^jaⁱ | i ≥ j ≥ 1 }

– (L₁)^R · (L₂)^R = { b^jaⁱ · (ε + a + aa) | i ≥ j ≥ 1 }

Exercice 4

1. Tout langage régulier est infini.
Faux. Par exemple, le langage composé d’un seul mot {ε} est régulier et fini.

2. Tout langage non régulier est infini.
Vrai. Raisonnement par contraposée : tout langage fini est régulier, donc tout langage non régulier est infini.

3. Il y a une infinité de langages réguliers.
Vrai, puisqu’il y a une infinité de langages finis et tout langage fini est régulier.

4. Tout langage inclus dans un langage régulier est régulier.
Faux. Par exemple Σ* sur l’alphabet Σ = {0, 1} est régulier. Cependant, le langage L ⊆ Σ* = { 0ⁿ1ⁿ | n ≥ 1 } est non régulier.

5. Si L* est régulier alors L est régulier.
Faux. La réciproque est vraie par construction des langages réguliers et de la fermeture de Kleene.

6. Il y a une infinité de langages non réguliers.
Vrai. L’ensemble des langages non réguliers est infini et même non dénombrable.

Exercice 5

(i) (b + ba)* : ε, b, bb, ba, bba, bbb, bbaa, baab, bbba, bbab, baba, bbaaa, bbaab, baab

(ii) ab* + b : a, b, ab, abb, abbb

(iii) (x_d + ε)* · d* : ε, d, ad, bd, dd, add, bdd, ddd, adad, adbd, badb, bdad, dadd, ddad, ddd

(iv) a* · (b + c) · d* : b, c, ab, ac, bd, cd, aab, aac, abd, acd, bdd, cdd, aaab, aaac, aabd, aacd, abd^d, acd^d, bdd^d, cdd^d

Exercice 6

(i) (a + b)* : l’ensemble de tous les mots sur l’alphabet Σ, ainsi que le mot ε.

(ii) a(a + b)* : l’ensemble de tous les mots qui commencent par le symbole a.

(iii) (a + b)*a : l’ensemble de tous les mots qui se terminent par le symbole a.

(iv) (aa + b)* : l’ensemble de tous les mots avec un nombre pair de a.

(v) (ab* a + b)* : l’ensemble de tous les mots avec un nombre pair de a.

Exercice 7

1. (a + b)(a + b)

2. ε + (a + b) + (a + b)(a + b) ou ε + (a + b)(ε + a + b) (règles d’équivalence)

3. ((a + b)(a + b))*

4. (a + b)*a(a + b)*

5. (a + b)*aba(a + b)*

6. ab(a^b)*

Exercice 8

1. (a + b) + (a + b)(a + b)* + ε* ≡ (a + b) + (a + b)(a + b)* + ε ≡ ε + (a + b) + (a + b)(a + b)* ≡ (a + b) + (a + b)(a + b)* ≡ (a + b)*

2. (x + y)ε + (x + y)ε* + ((x + y)*ε*)* ≡ ε + (x + y)ε* + ((x + y)*ε*)* ≡ (x + y)* ≡ (x + y) + ((x + y)*ε)* ≡ (x + y)*

3. 0(ε + 00)* (1 + 01) + 1 ≡ 0(00)*(1 + 01) + 1(ε + 0)* ≡ 0* ≡ 0(00)* + 0(00)*0 + ε)1(ε + 0)* ≡ 0(ε + 0)* ≡ 0*

FAQ

Qu’est-ce qu’un langage régulier ?

Un langage régulier est un ensemble de mots (chaînes de caractères) qui peut être reconnu par une machine à états finis (automate fini). Il est défini par une expression régulière.

Quelle est la différence entre Σ* et Σ+ ?

Σ* inclut tous les mots possibles sur l’alphabet Σ, y compris le mot vide ε. Σ+ exclut uniquement le mot vide ε.

Pourquoi la fermeture de Kleene est-elle importante ?

La fermeture de Kleene permet de construire des expressions régulières pour décrire des langages infinis à partir de langages finis. Elle inclut les opérations de concaténation, union et itération.