Tiêu đề °TD compilation SMI5 FST TETOUAN 2020.pdf ✅

Filière : SMI Série 1 Exercice 1 Décrire les langages définis par les expressions rationnelles suivantes (l'alphabet puis l'expression) : 1. A1 = {0,1,2,3,4,5,6,7,8,9,H}, ([1-9][0-9]* (0|2|4|6|8)) | (0|2|4|6|8) 2. A1, (0[0-9] |10 | 11 | 12)H[0-5][0-9] 3. A2 = {a, b, c}, ((a|b|c)(a|b|c)(a|b|c))* 4. A2, (a|b|c)*a(a|b|c)*a(a|b|c) 5. A2, (b|c)*a(b|c)*a(b|c)* Exercice 2 Pour chacune des expressions rationnelles suivantes, donner une expression rationnelle plus simple décrivant le même langage : 1. a + a*bc | aa?b?c 2. ([a-z]*)*(c(ab)* | ca(b(ab)*)) 3. a(ba)*b | (ab)+ cd 4. a(ba)*b(bc|c) | ab*b?c Exercice 3 Soit l’alphabet A = {0, 1, 2}. Résoudre le système suivant : X = 0X + 1Y + 1Z + 0 Y = 0Y + 1Y Z = 1Z + 0Y + 00
Exercice 4 Soient a et b deux expressions rationnelles. Montrer que : 1. a(a+ba)* = (a+ab)*a 2. (ab) * a = a (ba) * 3. (a+b)+ = a+ + a* (ba*)+ Exercice 5 Les langages suivants sont-ils rationnels ? M = {anb p : n < p, n, p  N } et L = {amb n c m+n / m, n  N}
Solution Exercice 2 1. a + a*bc | aa?b?c = a+ bc | aa?b?c : car a+ a* = a+ a (a*b | a?b?) c (on factorise a et c) a (a*b | a?) c : car a?b? = a | b | ab | ε or b et ab sont déjà dans a*b. 2. ([a-z]*)*(c(ab)* | ca(b(ab)*)) = [a-z]* c ((ab)* | a(b(ab)*)) : car x** = x*, de plus on factorise c = [a-z]* c ((ab)* | ab(ab)*) : car x(y) = xy = [a-z]* c ((ab)* | (ab)+ ) : car xx* = x+ = [a-z]* c (ab)* : car x*|x+ = x*, x+  x* 3. a(ba)*b | (ab)+ cd = (ab)+ | (ab)+ cd : car a(ba)*b = (ab)+ = (ab)+ (cd)? 4. a(ba)*b(bc|c) | ab*b?c = (ab)+ (bc|c) | ab* b?c : car a(ba)*b = (ab)+ (vue précédemment) = ((ab)+ b? | ab* b?)c = ((ab)+ | ab*)b?c Exercice 3 X = 0X +1Y + 1Z +0 Y = 0Y +1Y =  Z = 1Z +0Y +00 Z = 1Z + 00 = 1*00
X = 0X + 11*00 +0 = 0*(1+ 00 + 0) Exercice 4 1. a(a+ba)* = (a+ab)*a ? Par le lemme d'Arden, (a+ab)*a est solution de (a+ab)X+a. Donc si a(a+ba)* = (a+ab)*a alors (a+ab)a(a+ba)*+a=a(a+ba)* ? (a+ab)a(a+ba)*+a = (aa+aba)(a+ba)*+a = a(a+ba)(a+ba)*+a = a(a+ba)+ + a = a(a+ba)* CQFD 2. (ab)*a est la solution de l’équation X = (ab)X + a (ab)a(ba)* + a = ? a(ba)* aba(ba)* + a = a(ba) + + a = a((ba) + + 1) = a(ba)* 3. (a+b)+ = a+ + a* (ba*)+ ? (a+b)+ = (a+b)(a+b)* = (a+b)a*(ba*)* (en utilisant e1) = a+ (ba*)* + ba*(ba*)* = a+ (ba*)* + (ba*)+ = a+ (1+(ba*)+ ) + (ba*)+ = a+ + a+ (ba*)+ + (ba*)+ = a+ + (a + + 1) (ba*)+