Théorie des langages : Td 1 langages réguliers et expressions régulières
Télécharger PDFUniversité 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 : 1 Correction - TD 1 : Notions fondamentales de la théorie des langages / Langages réguliers et expressions régulières
Exercice 11) 퐿={ 푎2푛 푏
푛 / 푛≥0} ou퐿= {( 푎푎) 푛푏 푛 / 푛≥0} 2) 퐿={ 휎푛 ∙( 휎+휀) ∙휎푛 / 휎 ∈ 훴,푛≥0} ou퐿= {휎 푛
/ 휎 ∈ 훴,푛≥0} 3) 퐿={ 푢∙( 휎+휀) ∙푢푅 / 휎 ∈ 훴,푢∈훴∗ }
Exercice 2 휀, n'appartient à aucune langage 푎, appartient à 퐿2 , 퐿
3 et 퐿5 푎푏푏푎, appartient à 퐿2 푎푏푏푎푎푐푐, appartient à 퐿4 푎푏푎, appartient à 퐿
2 et 퐿3 푎푎푏푏, appartient à 퐿1 , 퐿2 , 퐿
6 et 퐿7 푎푏푏, appartient à 퐿2 , 퐿
3 et 퐿5
Exercice 3 퐿2 ∙퐿3 ={ 푎푏,푎푏푎,푎푎푏,푎푎푏푎,푏,푏푎} 퐿2 ∙퐿1 = 퐿1 퐿1 ∙퐿3 = {푎 푖푏 푗,푎 푖푏 푗
푎 / 푖≥푗−1≥1} ={ 푎푖 푏푗 ∙( 푎+휀
) / 푖≥푗−1≥1} 퐿5 ∩퐿1 = 퐿6 퐿6 ∪퐿5 = 퐿5 퐿1 ∙( 퐿2 ∩퐿4 )
= 퐿1 퐿1 ∙( 퐿2 ∩퐿3 )
= ∅ (퐿 1∙퐿 2) 푅
= {( 휀+푎+푎푎) ∙푏푗 푎
푖 / 푖≥푗≥1} (퐿 1) 푅∙ (퐿 2) 푅
= {푏 푗푎 푖∙ (휀+푎+푎푎 ) / 푖≥푗≥1}
Exercice 41. 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, alors, tout langage non régulier est infini. 3. Il y a une infinité de langages réguliers. 2 Vrai. puisqu'il y a une infinité des langages finis et tout langage fini est régulier, alors, Il y a une infinité de langages réguliers. 4. Tout langage inclus dans un langage régulier est régulier. Faux. Par exemple 훴
∗ sur l’alphabet 훴={ 0,1
} est régulier. Par contre, le langage 퐿 ⊆훴∗ ={ 0푛 1푛 / 푛≥1
} est non régulier 5. Si 퐿
∗ est régulier alors 퐿 est régulier. Faux. Pas forcément. 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) (푏 + 푏푎)
∗ : 휀,푏,푏푏,푏푎,푏푏푏,푏푏푎,푏푎푏,푏푏푏푏,푏푏푏푎,푏푏푎푏,푏푎푏푎,푏푎푏푏 (ii) 푎푏∗ + 푏 : 푎,푏,푎푏,푎푏푏,푎푏푏푏 (iii) (
푥푑 + 휀) ∗
푑 ∗ : 휀,푑,푎푑,푏푑,푑푑,푎푑푑,푏푑푑,푑푑푑,푎푑푎푑,푎푑푏푑,푏푑푏푑,푏푑푎푑,푑푑푎푑,푑푑푏푑,푎푑푑푑,
푏푑푑푑,푑푑푑푑 (iv) 푎∗ (
푏 + 푐) 푑
∗ : 푏,푐,푎푏,푎푐,푏푑,푐푑,푎푎푏,푎푎푐,푎푏푑,푎푐푑,푏푑푑,푐푑푑,푎푎푎푏,푎푎푎푐,푎푎푏푑,푎푎푐푑,
푎푏푑푑,푎푐푑푑,푏푑푑푑,푐푑푑푑
Exercice 6(i) (푎 + 푏)
∗ : l’ensemble de tous les mots sur l’alphabet 훴, ainsi que le mot 휀 (ii) 푎(푎 + 푏)
∗ : l’ensemble de tous les mots qui commencent par le symbole 푎 (iii) (푎 + 푏)∗ 푎 : l’ensemble tous les mots qui se terminant par le symbole 푎 (iv) (푎푎 + 푏)
∗ : l’ensemble tous les mots avec un nombre pair de 푎. (v) (푎푏
∗ 푎 + 푏)
∗ : l’ensemble tous les mots avec un nombre pair de 푎.
Exercice 71. (푎 + 푏)(푎 + 푏) 2. 휀+( 푎 + 푏) +(푎 + 푏)(푎 + 푏) ou 휀+( 푎 + 푏) (휀+푎 + 푏) (i.e. les règles d’équivalence) 3. ((푎 + 푏)(푎 + 푏))∗ 4. (푎 + 푏)∗ 푎(푎 + 푏)∗ 5. (푎 + 푏)∗ 푎푏(푎 + 푏)∗ 6. 푎푏(푎푏)∗
Exercice 81. (
푎 + 푏) + (
푎 + 푏)( 푎 + 푏) ∗ + ∅∗ ≡ (
푎 + 푏) + (
푎 + 푏)( 푎 + 푏) ∗
+ 휀∅ ∗ ≡ 휀 3 ≡ (
푎 + 푏) +휀+ (
푎 + 푏)( 푎 + 푏) ∗
훽+훼≡ 훼+훽 ≡ (
푎 + 푏) +( 푎 + 푏) ∗
휀+ 훼훼
∗ ≡ 훼∗ ≡ (
푎 + 푏) ∗훼+훼 ∗ ≡ 훼∗ 2. (
푥 + 푦) ∅ + (
푥 + 푦) ∅∗ + ((
푥 + 푦) ∗ ∅∗ )∗ ≡ ∅ + (
푥 + 푦) ∅∗ + ((
푥 + 푦) ∗ ∅∗ )∗ 훼∅ ≡ 휀 ≡ (
푥 + 푦) ∅∗ + ((
푥 + 푦) ∗ ∅∗ )∗ 훼+∅ ≡ 훼 ≡ (
푥 + 푦) 휀 + ((
푥 + 푦) ∗ 휀 )∗ ∅
∗ ≡ 휀 ≡ (
푥 + 푦
) + ((
푥 + 푦) ∗) ∗
훼휀≡훼 ≡ (
푥 + 푦
) + (
푥 + 푦) ∗( 훼∗ )∗ ≡훼∗ ≡ (
푥 + 푦) ∗훼+훼 ∗ ≡ 훼∗ 3. 0( 휀 + 00) ∗( 1 + 01) + 1 ≡0( 00) ∗( 1 + 01) + 1( 휀+훼) ∗ ≡ 훼∗ ≡0( 00) ∗( 휀+ 0) 1+ 1
(훼 + 훽)훾 ≡ 훼훾 + 훽훾 ≡(0( 00) ∗( 휀+ 0) +휀) 1
(훼 + 훽)훾 ≡ 훼훾 + 훽훾 ≡(0( 00) ∗+0 (00 )∗ 0+휀) 1
훼(훽 + 훾) ≡ 훼훽 + 훼훾 ≡(0+ +휀) 1
(vous pouvez vérifier que{ 0( 00) ∗} ∪{ 0( 00) ∗0 }= {0 +} ) ≡0
∗ 1
(vous pouvez vérifier que{ 0+ }∪ {휀 }= {0 ∗} )