Scribd
Importer
44 vues3 pages

Corrigé Rattrapage

Ce document contient les corrigés de plusieurs exercices sur la théorie des langages. Il présente les solutions détaillées à des exercices portant sur la reconnaissance de langages réguliers, la déterminisation d'automates finis et la construction de graphes de dérivation.

Transféré par

seyfeddine.hammami
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
44 vues3 pages

Corrigé Rattrapage

Ce document contient les corrigés de plusieurs exercices sur la théorie des langages. Il présente les solutions détaillées à des exercices portant sur la reconnaissance de langages réguliers, la déterminisation d'automates finis et la construction de graphes de dérivation.

Transféré par

seyfeddine.hammami
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université Chadli Bendjedid – El Tarf Module : Théorie des Langages

Faculté des Sciences et de la Technologie Durée : 1h15


Département d’Informatique Barème : /20

17/04/2017

EMD Théorie des Langages


Corrigé

Exercice 1 (4pts)
1. (𝑎 + 𝑏)∗ 𝑎(𝑎 + 𝑏)∗ : ensemble de tous les mots contenant au moins a (0.5pts)
𝑎, 𝑏 𝑎, 𝑏

𝑎 (0.5pts)

2. 𝑎𝑏 ∗ + 𝑏 : ensemble des mots contenant un seul 𝑎 et bornés par 𝑎 et 𝑏 (commençant par 𝑎 et se


terminant par 𝑏) (0.5pts)
𝑏
(0.5pts)
𝑎 𝑏

3. (𝑎 + 𝑐)∗ 𝑎𝑐(𝑏 + 𝑑)∗ 𝑎𝑏𝑎 : ensemble des mots contenant au moins une occurrence de la sous-
chaine 𝑎𝑐 et se terminant par la sous chaine 𝑎𝑏𝑎 (0.5pts)
𝑎, 𝑐 𝑏, 𝑑 (0.5pts)

𝑎 𝑐 𝑎 𝑏 𝑎

4. 𝑏 ∗ 𝑎(𝑎 + 𝑏)∗ 𝑏𝑎∗ : ensemble des mots contenant au moins une occurrence de 𝑎 et une occurrence
de 𝑏

𝑏 𝑎, 𝑏 𝑎
(0.5pts)
𝑎 𝑏

Exercice 3 (12pts)
a. Déterminisation : (2.5 pts)
𝛿(1, 𝜀) = 3 𝛿(2, 𝜀) = 3 𝛿(4, 𝜀) = 5 𝛿(5, 𝜀) = 6 𝛿(5, 𝜀) = 4
𝛿(3, 𝑎) = 5 𝛿(3, 𝑎) = 5 𝛿(5, 𝑎) = 5 𝛿(6, 𝑏) = 6 𝛿(4, 𝑏) = 5
𝜹(𝟏, 𝒂) = 𝟓 𝜹(𝟐, 𝒂) = 𝟓 𝜹(𝟒, 𝒂) = 𝟓 𝜹(𝟓, 𝒃) = 𝟔 𝜹(𝟓, 𝒃) = 𝟓
ε, a
2 4
a a

ε, b b ε, b
1
a
a
ε,b 3 5
a

a b
1 {1,2} 3
2 {4,5} {3,5} (1.0pts)
3 5 ∅
4 {5,6} 5
5 {5,6} {2,5,6}
*6 ∅ 6

a. Construire un automate 𝑇3 déterministe, équivalent à 𝑇2 . (3pts)

a b
1 {1,2} 3
{1,2} {1,2,4,5} {3,5}
3 5 ∅
{1,2,4,5} {1,2,4,5,6} {2,3,5,6}
{3,5} {5,6} {2,5,6}
5 {5,6} {2,5,6}
∗ {1,2,4,5,6} {1,2,4,5,6} {2,3,5,6}
∗ {2,3,5,6} {4,5,6} {2,3,5,6}
∗ {5,6} {5,6} {2,5,6}
∗ {2,5,6} {4,5,6} {2,3,5,6}
∗ {4,5,6} {5,6} {2,5,6}
(2pts)
a b
1 2 3
2 4 5
3 6 ∅
4 7 8
5 9 10
6 9 10
∗7 7 8
∗8 11 8
∗9 9 10
∗ 10 11 8
∗ 11 9 10

Exercice 4 (4pts)
a. 𝐺1 = (𝛴, 𝑉, 𝑆, 𝑅) 𝑎𝑣𝑒𝑐 𝛴 = {𝑎, 𝑏, 𝑐}, 𝑉 = {𝑆, 𝐴}, 𝑆 = {𝑆},
𝑅 = {𝑆 → 𝑎𝐴𝑎𝑐} ∪ {𝐴 → 𝑆𝑏|𝑏𝑏}
Ensemble des mots commençant par 𝒂 et se terminant par la sous-chaine 𝒂𝒄 (2pts)
b. 𝐺2 = (𝛴, 𝑉, 𝑆, 𝑅) 𝑎𝑣𝑒𝑐 𝛴 = {𝑎, 𝑏, 𝑐, 𝑑}, 𝑉 = {𝑆, 𝑋}, 𝑆 = {𝑆},
𝑅 = {𝑆 → 𝑏𝑋} ∪ {𝑋 → 𝑋𝑏𝑎|𝑐𝑎|𝑑𝑎}
Ensemble des mots commençant par 𝒃 et se terminant par 𝒂 (2pts)

Vous aimerez peut-être aussi