Exercice 1 Exercice 2

Universit´
e Mohamed Premier
Facult´
e des Sciences
Oujda
Fili`
ere SMI-S5
Ann´
ee universitaire 2014-2015
Module Compilation
Feuille de TD N◦ 1
Exercice 1
On dit que deux expressions r´eguli`eres r et s sont ´egales, et l’on ´ecrit r = s,
si et seulement si L(r) = L(s). D´emontrer les identit´es suivantes :
1. r | ∅ = ∅ | r = r.
2. r∅ = ∅r = ∅.
3. rε = εr = r.
4. ∅∗ = ε∗ = ε.
5. r | s = s | r.
6. (r | s) | t = r | (s | t).
7. r(s | t) = rs | rt.
8. (r | s)t = rt | st.
9. (rs)t = r(st).
10. rr∗ | ε = r | r∗ = ε | r∗ = (r∗ )∗ = r∗ .
Exercice 2
Sur l’alphabet A = {0, 1}, ´ecrire des expressions r´eguli`eres qui d´enotent les
langages suivants :
1. Toutes les chaˆınes qui se terminent par un 0.
2. Toutes les chaˆınes contenant au moins un 1.
3. Toutes les chaˆınes contenant au plus un 1.
4. Toutes les chaˆınes telles que la troisi`eme position `a partir de la droite soit
occup´ee par un 1.
5. Toutes les chaˆınes ayant un nombre pair de 0.
6. Toutes les chaˆınes telles que toutes les s´eries de 1 aient une longueur paire.
7. Toutes les chaˆınes telles que deux caract`eres cons´ecutifs ne soient pas identiques.
1
Exercice 3
´
Etant
donn´ee l’expression r´eguli`ere r = a∗ (a | b)aa :
1. Construire un AFND ´equivalent `a r en utilisant l’algorithme de Thompson.
2. Convertir l’AFND obtenu en un AFD ´equivalent en utilisant l’algorithme
vu dans le cours.
Exercice 4
Trouver des AFD qui reconnaissent les langages suivants :
1. Toutes les chaˆınes sur {a, b} ayant un nombre pair de a et un nombre
impair de b.
2. Toutes les chaˆınes d´esignant des entiers en base 10 divisibles par 3. Les 0 `a
gauche sont interdits.
3. Toutes les chaˆınes binaires qui repr´esentent des entiers qui sont des multiples
de 5. Les 0 `a gauche sont interdits.
Exercice 5
Consid´erons l’AFD M suivant :
1. Donner les ´el´ements de M .
2. Simplifier l’automate M .
3. En utilisant l’algorithme de Moore, minimiser l’automate M .
4. En d´eduire une expression r´eguli`ere qui d´enote L(M ), le langage reconnu
par M .
5. Construire un AFD qui reconnaˆıt le langage (L(M ))2 .
2

Download Report