Correction TD1
Exercice1
1) W1=01,w2=101
W1.w2=01101
W2.w1=10101
W13 =010101
W22=101101
ɛ.w1=w1=01
|w1|=2
2) Les mots suivants générés par l'expression régulière (ab*)b* : a,abbb
Exercice2 :
1. a(a|b)*b : ab,abb,aab,abab,aaab…
2. (a|b)*ab(a|b)*:ab, aaba,babb,aabb,baba….
3. (aa)*a: a,aaa,aaaaa..(nombre impair de a)
4. (a|b)*(c|d)*: ɛ,a,b,c,d,ac,abcd…
5. aab(a|b)*(bb|aa)+ : aabaa,aabbb,aabaabbbb…
6. (a|ab)(c|bc) : {ac,abc,abbc}
Exercie3:
1)
W1 et w2 sont définis sur ∑1
W3 est défini sur ∑1 et ∑3
W4 est défini sur ∑1 et ∑2
W5 est défini sur ∑1
W6 est défini sur ∑1
2) La taille de w1 sur ∑1 est 3
La taille de w2 sur ∑1 est 4
La taille de w3 sur ∑1 est 8 et sur ∑3 est 2
La taille de w4 sur ∑1 est 4 et sur ∑2 est 2
La taille de w5 sur ∑1 est 11
La taille de w6 sur ∑1 est 9
3) Il faut ajouter les mots : erat,t
4) Bali les suffixes {ɛ,i,li,ali,bali}
Les préfixes de taam{ɛ,t,ta,taa,taam}
Exercice4 :
On considère l’alphabet {a,b}, donner une expression régulière décrivant :
1. les mots qui commencent par b : b (a|b)*
2. les mots qui contiennent exactement trois a : b* a b* a b* a b*
3. les mots qui contiennent au moins trois a : (a|b)*a(a|b)*a(a|b)* a(a|b)*
b*a b*a b*a(a|b)*
4. les mots qui contiennent au plus trois a : b*|b* a b*| b* a b* a b*| b* a b* a b* a b*
b*(a|¤)b*(a|¤)b*(a|¤)b*
5. les mots qui ne contiennent pas la séquence ab : b* a *
Exercice 5
1. les mots qui ne contiennent pas deux 0 successifs.
(1|01)*(0| ɛ) ((0| ɛ)1+)*(0| ɛ)
2. les mots qui ne contiennent pas la séquence 100.
0*(1|10)*
3. les mots de longueur paire.
((0|1). (0|1))*
4. les mots ayant un nombre pair de 0 et un nombre pair de 1.
Langage non régulier pas d’expression régulière
5. les mots formés d’alternances de 0 et 1.
(1| ɛ) (01)*(0| ɛ)
6. les nombres multiples de 2 et plus grands ou égaux à 8.
Langage non régulier pas d’expression régulière
Exercice6 :
On considère l'alphabet {a, b}. Donner les expressions régulières correspondantes aux
propriétés suivantes :
1. les mots qui ne contiennent aucun b : a*
2. les mots qui contiennent au moins un a : (a|b)*a(a|b)*
b*a(a|b)*
3. les mots de longueur paire : (aa|bb|ba|ab)*
((a|b). (a|b))*
4. le langage L = { bnpn} avec n et p entiers et au moins l'un des deux impair :
(bb)*b(aa)*|(bb)*(aa)*a|(bb)*b(aa)*a
(bb)*(b|ɛ)(aa)*a | (bb)*b(aa)*(a|ɛ)
5. les mots formes d'alternance de a et de b.
(ab)*(a|ɛ) |(ba)*(b|ɛ)
6. les mots qui ne contiennent pas aa.
a(b+ab*|b*)*|(b+ab*|b*)*
(b|ab)*(a| ɛ) ((a| ɛ)b+)*(a| ɛ)
b*(ab+)*(a| ɛ)
(ab+)*(a| ɛ) | (b+a)*(b*| ɛ)
Exercice 7 :
1) Non, car le plus petit mot dans w1 est
Le plus petit mot dans w2 est bcw avec 1<|w|<2
2) L1 : a+
L2 : u=bcw / 3<|u|<4
3) M11=aaa
M12=aaaaa
M21=bcb
M22=bcab
4) M=M11.M22=aaabcab,|m|=7
Exercice 8 :
1) Aba, aaba…
2) Ba,ɛ…
3) L’ensemble vide
4) Abb…
Exercice 9 :
1) {uϵ∑/ u=ur }
2) { uϵ∑/|u|=2k,kϵN}
3) { uϵ∑/|u|b=2k+1,kϵN}
4) { uϵ∑/|u|<8 et |u|a=2k,kϵN }
Exercice 10
L1∩L2={aba,aaba,abaa}
L1-L3={ɛ,a,b,ab,aba,aaba,abba}
Exercice 11
1)
L1.L2={a,ab,aba,abb,abba,ba,bab,baba}
L2.L1={a,ab,ba,bab,bba,baa,baab,baba}
L1.Ø= Ø
Ø.L2= Ø
L1.ɛ=L1
ɛ.L2=L2
L2∩ɛ={ɛ}
2) L3=L4=ɛ
L3=Øou L4=Øou L3=L4=Ø
