Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
Correction TD 2
Exercice 1.
Quels sont les langages décrits par les ER suivantes?
(i) a(a|b)*b (ii) (aa)*a (iii) (a*|b*)*
(iv) (a|b)*(c|d)* (v) ((ε|b)a+)* (vi) aab(a|b)*(bb|aa)+
Corrigé :
(i) Les mots sur l’alphabet {a, b} qui commencent par a et se terminent par b.
(ii) Les mots sur l’alphabet {a, b} formés par un nombre impair de a.
(iii) Tous les mots sur l’alphabet {a, b}.
(iv) Les mots sur l’alphabet {a, b, c, d} dont chacun est une concaténation d’un mot sur
l’alphabet {a, b} et un mot sur l’alphabet {c, d}.
(v) Les mots sur l’alphabet {a, b} dont chaque puissance de a est précédée par, au plus, un
b.
(vi) Les mots sur l’alphabet {a, b} qui commencent par aab et se terminent par un nombre
na pair de a et un nombre nb pair de b, na+ nb≠0.
Exercice 2.
Donnez une ER décrivant :
(i) Les mots sur {a, b, c}
(ii) Les mots sur {a, b, c} qui commencent par b
(iii) Les mots sur {a, b, c} qui contiennent exactement trois a
(iv) Les mots sur {a, b, c} qui contiennent au moins trois a
(v) Les mots sur {a, b, c} qui contiennent le facteur babb au moins deux fois
(vi) Les mots sur {a, b} qui ne contiennent pas le facteur ab
Corrigé :
(i) (a|b|c)*
(ii) b(a|b|c)*
(iii) (b|c)*a(b|c)*a(b|c)*a(b|c)*
(iv) (a|b|c)*a+( a|b|c)*a+( a|b|c)*a+( a|b|c)* ou (a|b|c)*a( a|b|c)*a( a|b|c)*a( a|b|c)*
(v) (a|b|c)*(babb)+(a|b|c)*(babb)+(a|b|c)*
(vi) b*a*
Exercice 3.
Donnez une ER décrivant :
(i) Les nombres entiers multiples de 5.
(ii) Les nombres binaires.
(iii) Les nombres hexadécimaux.
(iv) Les nombres réels.
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
Corrigé :
(i) (0|1| … |9)*(0|5)
(ii) (0|1)*
(iii) (0|1| … |9|A|B| … |F)*
(iv) (0|1| … |9)* . (0|1| … |9)*
Exercice 4.
Donnez une ER décrivant :
(i) Les mots sur {a,b} de longueur paire
(ii) Les mots sur {a,b} ayant un nombre pair de a et un nombre pair de b
Corrigé :
(i) (aa|ab|ba|bb)*
(ii) (a(bb)*a | b(aa)*b | baba | abab)*
Exercice 5.
Donnez une expression régulière décrivant :
(i) Les mots sur {a,b,c} qui ne possèdent pas le facteur ab et possèdent exactement deux c
(ii) Les mots sur {a,b,c} qui ne possèdent pas le facteur ab et possèdent au moins deux c
Corrigé :
(i) b*a*c b*a*c b*a*
(ii) (c*b*c*a*c*)c+(c*b*c*a*c*)c+(c*b*c*a*c*) (c*b*c*a*)c+(b*c*a*)c+(b*c*a*c*)
Exercice 6.
Soit X = {a , b}
On définit récursivement les mots de X* appelés « SPEC» comme suit :
w est un SPEC si et seulement si : w = b ou w = w1 a w2, avec w1 et w2 des SPECS.
On note T le langage de tous les SPECS.
4) Déterminer les SPECS de longueur 5.
5) Démontrer que tout SPEC w s’écrit sous la forme : w = b(ab)n pour n 0.
6) Démontrer que tout w = b (ab)n pour n 0, est un SPEC.
Corrigé :
1) SPECS de longueur 5 : {b,bab,babab}
2) Preuve par induction généralisée :
Soit la propriété P(l) : l 0(Si w est un SPEC de longueur l, alors n 0 tel que w =
b(ab)n)
- Base d’induction généralisée : Vérifions que P(l0) est vraie. l0 est la plus petite
longueur pour laquelle la propriété est vérifiée.
Le plus petit SPEC est w =b de longueur l0=1; w = b (ab)0 donc n tel que w = b(ab)n
donc P(1) vraie
- Etape d’induction généralisée:
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
Montrons que l(l0≤k<l ; P(k)P(l))
(En d’autre termes, supposons que la propriété est vraie pour toutes les longueurs < l
et montrons qu’elle est vraie pour l)
Soit w un SPEC de longueur l.
w = w1 a w2, avec w1 et w2 des SPECS.
|w1|<|w| donc n1 tel que w1 = b(ab)n1
|w2|<|w| donc n2 tel que w2 = b(ab)n2
w = w1 a w2 = b(ab)n1 a b(ab)n2 = b(ab)n1+n2+1
donc n tel que w = b(ab)n
Conclusion : P(l) vraie
3) Preuve par induction simple (récurrence):
Soit la propriété P(n) : Si w = b (ab)n ; n 0, alors w est un SPEC.
- Base d’induction : Vérifions que P(0) est vraie.
n=0 ; w = b (ab)0=bSPEC
P(0) vraie
- Etape d’induction :
Montrons que n
Supposons que P(n) est vraie et montrons que P(n+1) est vraie
w = b (ab)n+1= b (ab)n(ab) =(b (ab)n)a(b)
w s’écrit sous la forme w1 a w2, avec w1 et w2 des SPECS. En effet w1= b (ab)n est un
SPEC car P(n) est vraie et w2=b est un SPEC.
Par conséquent, P(n+1) est vraie
Conclusion : n 0 ; P(n) vraie
Exercice 7.
Calculer L2 puis L* dans les cas suivants :
1. L = {xpyp / p 0}
2. L = {w / d(w) = 0}
3. L = (xy)*
4. L = {w / |w| = 2k + 1, k 0}
5. L = {w / |w| = 2k, k 0}
Corrigé :
1. L2 = {xp1yp1 xp2yp2 / p1 0 ; p2 0}
Li = {xp1yp1 xp2yp2… xpiypi / p1 0 ; p2 0 ;… ; pi 0}
L* =
2. L* = L2 = L (L2 = {w=w1w2/d(w1) et d(w2)=0})
3. L2 = {(xy)p1 (xy)p2 / p1 0 ; p2 0}
Li = {(xy)p1 (xy)p2… (xy)pi / p1 0 ; p2 0 ;… ; pi 0}
L* =
4. L2 = {w / |w| = 2k , k > 0}
L*= L L2
* 2
5. L =L =L
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
Exercice 8.
Sur l’alphabet X = {x, y} construire des automates finis déterministes reconnaissant les
langages suivants :
L1 = x*
L2 = x+
L3 = x*y*
L4 = x+y+
Vérifier en utilisant le lemme d’Arden
Corrigé :
Lemme d’Arden :
Les deux équations L=AL+B et L=LA+B avec A et B deux langages et L’inconnue de l’équation
ont respectivement comme solution minimale A*B et BA*. De plus, si A ne contient pas alors
cette solution est unique. Exemple : L={a}L+{a,b}
D’après le lemme d’Arden : L={a}*{a,b}={a*a, a*b}=a++{a*b}
L1 = x*
q0 = {x }q0 + {} = x* = x*
L2 = x+
q0 = {x}q1 (1)
q1 = {x}q1 + {} (2)
(1) +(2) : q0 = {x}({x}q1 + {}) = x*x + x* = x+ + = x+
L3 = x*y*
q0 = {x} q0 + {y} q1 + {} (1)
q1 = {y}q1 +{} = * (y*) = y* (2)
(1) +(2) : q0 = {x} q0 + q1 = {x} q0 + y* = (x) * (y*) = x*y*
L4 = x+y+
q0 = {x} q0 + {x} q1 = {x} q0 + {x} y+ = (x) * (x y+) = x+y+
q1 = {y} q2 = y y* = y+
q2 = {y} q2 +{} = y*
on a résolu le q2 puis le q1 et finalement le q0.
Exercice 9.
1) Déterminer des automates finis déterministes reconnaissant les langages suivants :
X = {a, b, c}
L1 = {w X* / w contient un facteur abc}
L2 = {w X* / w se termine par aabb}
X = {0, 1}
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
L3 = {w X* / n(w) = 3k + 1, k 0} avec w est la représentation binaire de
n(w)
L4 = l’ensemble des mots tels qu’il y ait soit deux 0 soit deux 1 consécutifs
3) En déduire des expressions régulières pour chacun des langages L1, L2, L3 et
L4.
Corrigé :
1) X = {a, b, c}
L1 = {w X* / w contient un facteur abc}
RL1 = (a|b|c)* abc (a|b|c)*
Après la méthode de déterminisation des automates finis non déterministes ;
a
a b c a,b ,c
Q0 Q1 a Q2 Q3
c
b
b ,c
L2 = {w X* / w se termine par aabb}
RL2 = (a|b|c)* aabb
(Après la méthode de déterminisation des automates finis non déterministes, on va
dessiner l’automate)
X = {0, 1}
L3 = {w X* / n(w) = 3k + 1, k 0} avec w est la représentation binaire de
n(w)
RL3 = (0)* 1 (1(0)*1| 0(1)*0)*
(Après la méthode de déterminisation des automates finis non déterministes, on va
dessiner l’automate)
L4 = l’ensemble des mots tels qu’il y ait soit deux 0 soit deux 1 consécutifs
RL4 = (0|1)* (11|00)(0|1)*
(Après la méthode de déterminisation des automates finis non déterministes, on va
dessiner l’automate)
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
Exercice 10.
Rendre déterministe l’automate suivant :
M = ({q, r, s}, {a, b}, q, {s}, {(q, b, q), (q, a, r), (q, a, s), (r, a, q), (r, a, r), (s, a, s), (s, a, q), (s,
b, r)})
Minimiser l’automate suivant :
M1 = ({1, 2, 3, 4, 5}, {a, b}, 1, {4}, {(1, a, 2), (2, a, 3), (3, b, 4), (4, a, 5), (5, b, 4)})
Corrigé :
1) Rendre déterministe l’automate M
a B
A=q {r,s} Q
B = {r,s} {r,q,s} R
C = {r,q,s} {r,q,s} {q,r}
D=r {q,r} -
E = {q,r} {q,r,s} Q
On va dessiner l’automate M avec la transition : {D,b,Puit}
2) Minimiser l’automate M1
Etape 1 : rendre M1 déterministe en premier lieu puis le minimiser, dans notre cas il est
déterministe, il suffit d’ajouter l’état puits P
Etape 2 : travailler la minimisation en utilisant cette méthode
Ensemble d’états non finaux Ensemble d’états finaux
0 {1,2,3,5,P} {4}
1 {1,2,P}{3,5} {4}
2 {1,P}{2}{3,5} {4}
3 {1}{P}{2}{3,5} {4}
4 {1}{P}{2}{3,5} {4}
Arrêt de l’algorithme de minimisation car l’étape 3 = l’étape 4.
Conclusion : fusionner les états 3 et 5 en un seul état puisqu’ils ont le même
comportement
Exercice 11.
4) Donner une grammaire qui génère les mots palindromes sur {a, b}
5) Donner une grammaire qui génère des formules bien formées de la logique des
propositions sur le vocabulaire {pr,, , , } où pr désigne une proposition
6) Donner une grammaire qui génère des expressions arithmétiques sur les nombres
entiers
Corrigé :
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
1) Les mots palindromes sur {a,b} :
G = {(S), (a,b), S, P} où
P = { S |a|b|aSa|bSb}
2) Les formulas de la logique des propositions :
G = {(S,C), (pr,, , , ), S, P} où
P = { S SCS | S
S pr
C | |
}
3) Les expressions arithmétiques sur les nombres entiers :
G = {(S,E,int,chiffre), (+,-, *, /, (0..9)), S, P} où
P = { S SCS | S
S E
E E+E
E E-E
E E*E
E E/E
E int
int chiffre int
int chiffre int |
chiffre 0 | … |9
Exercice 12.
1) Soit G la grammaire définie par G = ({S}, {a, b, c}, S, P) où
P = { S | aSb }
Montrer L(G) = {anbn / n 0}
2) Donner une grammaire, non contextuelle, G1 qui génère L(G) {anb2n / n > 0}
Corrigé :
1) On va montrer L(G) = {anbn / n 0} ; on va vérifier par induction
simple (récurrence):
Soit la propriété P(n) : Si w = anbn ; n 0, alors w est vraie.
- Base d’induction : Vérifions que P(0) est vraie.
n=0 ; w = a0b0= L(G)
P(0) vraie
- Etape d’induction :
Montrons que n
Supposons que P(n) est vraie et montrons que P(n+1) est vraie
w = a n+1bn+1= a a n b bn
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
w s’écrit sous la forme w1 a w2, avec w1 et w2 des mots. En effet w1= a (a)n est un
mot accepté car P(n) est vraie et w2=b(b)n est un mot accepté.
Par conséquent, P(n+1) est vraie
Conclusion : n 0 ; P(n) vraie
2) G1 qui génère L(G) {anb2n / n > 0}
Soit X = {a,b}
L1, L2 inclus et égale X*
L1 = {anbn / n 0}
L2 = {anb2n / n > 0}
L1 L2 = {w X* | w L1 ou w L2}
G1 = ({S}, {a,b}, S, P) où
P = { S aS1b|aS2bb|
S1 aS1b|
S2 aS2bb|
}
Exercice 13.
Soit L1 = {w {a, b}* / w commence par a et se termine par bb}
5) Déterminer un automate fini déterministe qui reconnaît L1
6) Montrer que le langage L1 est régulier
7) Donner une grammaire régulière G1 qui génère le langage L1
8) Donner une grammaire G qui génère L1.L2 où L2 = {cn / n 0}
Corrigé :
1) L’automate fini déterministe du L1 :
a b
a b b
Q0 Q1 Q2 Q3
a
b a
P a, b
2) Il existe un AFD qui reconnaît L1 donc L1 est régulier
3) Une grammaire régulière G1 qui génère le langage L1 :
G1 ={V, (a, b), Q0, R}
V = {Q0, Q1, Q2, Q3, P}
R= {
Q0 aQ1 | bP
P aP | bP
Q1 aQ1| bQ2
Q2 aQ1| bQ3
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
Q3 aQ1| bQ3 |
}
4) Une grammaire G qui génère L1.L2 :
G ={V, (a, b, c), Q0, R}
V = {Q0, Q1, Q2, Q3, Q4, P}
R= {
Q0 aQ1 | bP | cP
P aP | BP | cP
Q1 aQ1| bQ2 | cP
Q2 aQ1| bQ3 | cP
Q3 aQ1| bQ3 | | cQ4
Q4 cQ4 |
}
Exercice 14.
1) Donner une grammaire qui génère des programmes de la forme
program test
a : integer;
b: float;
begin
a := 1;
b:= 3;
if a> 2 then a:= 4; else b := 1 endif;
end;
Les seules instructions autorisées sont l’affectation et la conditionnelle. L’alphabet terminal
sera :
T = { program, integer, float, begin, end, if, then, else, endif, : , :=, ;, >, =, idf, constantes}
Idf représente tout identificateur alphanumérique qui commence par un caractère alphabétique
et constantes représente toute constante numérique.
Corrigé :
G = (V,T,S,R)
J’ai enrichi l’ensemble T par d’autres terminaux
R={
S program idf DCL begin INST end;
DCL L_idf : Type ; | L_idf : Type ; DCL
L_idf idf | idf, L_idf
Type integer | float
INST Inst_affec | Inst_cond | Inst_affec INST | Inst_cond INST
Inst_affec idf := EXP; | idf := EXP; Inst_affec
Année Universitaire : 2016-2017
Module : TLC 2ème année Licence Fondamentale en
Informatique et Multimédia
EXP idf | constante | EXP oparith EXP | (EXP)
oparith + | - | * | /
Inst_cond if (COND) then INST endif; | if (COND) then INST endif; Inst_cond |
if (COND) then INST else INST endif; | if (COND) then INST else INST endif;
Inst_cond
COND EXP oprel EXP
oparel > | >= | < | <= | = | !=
}
Remarque1 : idf n’est pas un terminal
idf lettre Alphanum
Alphanum lettre Alphanum | chiffre Alphanum |
lettre a | …| z | A | … | Z
chiffre 0 | … |9
Remarque2 : constante n’est pas un terminal (exemple : l’ensemble des nombres entiers)
constante chiffre Nb |
NB chiffre NB | |
chiffre 0 | … |9
