Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

SMI6 (2009 – 2010) Théorie des langages & Compilation Eléments de correction de

SMI6 (2009 – 2010) Théorie des langages & Compilation Eléments de correction de la série 1 EX.1 Succ = {(n, n+1) / n ∈ℕ}. Succ est une relation binaire sur ℕ (Suuc ⊂ ℕxℕ). 1) Succ n'est pas réflexive : ∀ n ∈ ℕ, (n, n) ∉ Succ. Succ n'est pas transitive : (x, y) ∈ Succ ⇒ y = x + 1 (1) (y, z) ∈ Succ ⇒ z = y + 1 (2) De (1) et (2) on en déduit que z = x + 2 et donc (x, z) ∉ Succ. 2) Succ* : Fermeture réflexive et transitive de Succ Succ* = ∪n ≥0 Succn, avec Succ0 = {(n, n) / n ∈ ℕ}. On a : ∀ (x, y) ℕxℕ, (x, y) ∈ Succn ⇔ y = x + n ( par rec. Sur n) Et Succ* = {(n, m) / m ≥ n} (démonstration par double inclusion). EX.2 V = {a, b}. (V*, .) est un monoïde (le produit est associatif, l'élément neutre est le mot vide noté ε}. A = {u ∈ V* / u ≡ 0 (2)} est un sous monoïde de V*. B = { u ∈ V* / u ≡ 1 (2)} n'est pas un sous un monoïde car le produit n'est pas stable (∀u, v ∈ B, u v ∉ B) et ε ∉ B. C = {(ab)n , n ∈ ℕ} et D = {an bn , n ≥ 0}ne sont pas des sous monoïdes car le produit n'est pas stable. E = {u ∈ V* / ua = ub} est un sous monoïdes de V*. EX.3 ∑ = {a, b}. L1 ={ u ∈ Σ* / |u|a = |u|b }, L2 = { u ∈ Σ* / |u| ≡ 1 mod. 2}, L3 = { an bm / n, m ∈ ℕ*} - L1 ∩ L2 = ∅ Du fait que tout mot de L2 est de longueur impaire et tout mot de L1 est de longueur paire (si u ∈ L1 alors u = |u|a + |u|b = 2 |u|a) - L1 ∩ L3 = { an bn , n ≥ 0} u ∈ L1 ∩ L3 ⇔ ∃ n , m ∈ ℕ : u = an bm et |u|a = |u|b u = an bm et |u|a = |u|b est équivalent à u = an bn. - ∑* \ L3 = ∑* ba ∑* (tout mot qui n'appartient pas à L3 contient nécessairement un b suivi de a) EX.4 Soit Σ un alphabet et soit ϕ : Σ* → Σ* telle que ϕ(ε) = ε et ϕ(ua) = a ϕ(u),∀ a ∈ Σ, ∀ u ∈ Σ*. 1) Montrer que : a) ϕ(a) = a ∀ a ∈ Σ. b) ϕ(u)= u ∀ u ∈ Σ. c) ϕ(u v) = ϕ(v) ϕ(u) , ∀ u , v ∈Σ*. d) ϕ(ϕ(u)) = u ∀ u ∈ Σ*. a) ϕ(a) = a ϕ(a) = ϕ(ε.a) = a ϕ(ε) = a . ε = a b) ϕ(u) = u par réc. Sur u. - pour u = ε Vrai. - H.R. : ϕ(u) = u pour tout mot u de longueur ≤ n. Soit v = u a un mot de longueur n + 1 (u = n). ϕ(v) = ϕ(u a) = (a ϕ(u) = a + ϕ(u) = 1 + u = v. c) ϕ(u v) = ϕ(v) ϕ(u) ∀u, v ∈ ∑* par récurrence sur v - vrai pour v = ε - H.R. vrai pour tout mot v' t.q. v' = n Elle est vérifiée pour v t.q. v = v' a. d) ϕ(ϕ(u)) ∀u ∈ ∑* Aussi par réc. Sur u. - ϕ(ϕ(ε)) = ε - u ≥ 1 ⇒ ∃ a ∈∑, ∃ v ∈ ∑* : u = v a ϕ(ϕ(u) = ϕ(ϕ(va)) = ϕ(aϕ(v)) = ϕ(ϕ(v)) ϕ(a) = ϕ(ϕ(v)) a (H.R.) = v a = u 2) Caractérisation de {u ∈ ∑* / u = ϕ(u)}= L . ϕ(ε) = ε , ε ∈ L . u = a1 a2, u = ϕ(u) ⇒ a1 a2 = a2 a1 ⇒ a1 = a2 (aa ∈L) . u = a1 a2 a3 , u = ϕ(u) ⇒ a1 = a3 (aba ∈ L) . u = a1 a2 a3 a4 , u = ϕ(u) ⇒ a1 = a4 et a2 = a3 ( abba ∈ L) . u = a1 a2 a3 a4 a5 , u = ϕ(u) ⇒ a1 = a5 et a2 = a4 (abcba ∈ L) On constate que L est l'ensemble des mots miroirs et que tout mot miroir s'écrit sous la forme : v ϕ(v) pour les mots miroirs de long. Paire ou v a ϕ(v) pour les mots miroirs de long. Impaire. (ϕ est l'image miroir d'un mot i.e. mot retourné) On pose M = {u ϕ(u) , u ∈ ∑*} ∪ {u a ϕ(u) , u ∈ ∑*, a ∈ ∑} et on montre que L = M. * M ⊆ L . Soit w ∈ M, deux cas : - w = u ϕ(u) , u ∈ ∑* ϕ(w) = ϕ(uϕ(u)) = ϕ(ϕ(u)) ϕ(u) = u ϕ(u) ⇒ w ∈ L - w = u a ϕ(u) , u ∈ ∑*, a ∈ ∑ ϕ(w) = ϕ(uaϕ(u)) = ϕ(ϕ(u)) ϕ(ua) = u ϕ(ua) = u a ϕ(u) = w ⇒ w ∈ L. * L ⊆ M. Soit w ∈ L. w ∈ L ⇒ w = ϕ(w). Deux cas à considérer: - si w est pair, alors w = u v avec u = v ( u = v ⇒ u = ϕ(u)= v= ϕ(v)) w = ϕ(w) ⇒ u v = ϕ(uv) = ϕ(v) ϕ(u) u v = ϕ(v) ϕ(u) ⇒ u = ϕ(v) et v = ϕ(u) ( du fait que u = ϕ(v) et v = ϕ(u)) w = u v = u ϕ(u) ⇒ w ∈ M - si w est impair, alors w = u a v (où a est une lettre de ∑ et u, v des mots de ∑*) avec u = v. w = ϕ(w) ⇒ u a v = ϕ(v) a ϕ(u) ⇒ u = ϕ(v) et v = ϕ(u) ( du fait que u = ϕ(v) et v = ϕ(u)) w = u a v = u a ϕ(u) ⇒ w ∈ L. EX.5 1) Vérifier si le mot 011100 appartient au langage décrit par l'expression régulière (0 + (11)*)*. u ∈ ( 0 + (11)*)+ ⇒ ∃ k > 0 : u ∈ (0 + (11)*)k u ∈ (0 + (11)*)k ⇒ ∃ u1, u2, …, uk ∈ (0 + (11)*) : u = u1 u2 …uk ui ∈ (0 + (11)*) ⇒ ui1 est pair ⇒ u1 est pair; Pour u = 011100, on a u1 = 3. Donc u n'est pas un mot de l'expression régulière. 2) Expression régulière pour: - L0 = {a, b, aa, ab, ba, bb} → a + b + aa + ab + ba + bb = A + b + a(a + b) + b(a + b) = (a + b) ( ε + a + b) - L1 = { a3n b2m+1 ∈ {a,b}*, n, m ≥ 0} = {(a3)n , n ≥0}{(b2)m , m ≥0}{b} = ∪n≥0 {(aaa)n} (∪m≥0 {(bb)m}) {b} = (aaa)* (bb)* b - L2 = {an bm / n + m ≡ 0 (2)} (n + m ≡ 0 (2) ⇔ n et m ont même parité (les deux pairs ou les deux impairs) - L2 = {(a)2k (b)2k' , k, k' ≥ 0} ∪ {(a)2i+1 (b)2j+1 i, j ≥ 0} = (aa)* (bb) + a(aa)* (bb)*b (même méthode utilisée dans L1) - L3 = {u ∈ (a + b)* / u ne contient qu' un seul b} u ∈ L3 ⇔ u s'écrit sous la forme : u = an b am avec n, m ≥ 0 (du fait que ub =1) ⇔ u ∈ a* b a* D'où l'exp. Rég. dénotant L3 est a* b a*. - L4 = { u ∈ (a + b)* / u commence par a et se termine aa} Le plus petit mot de L4 est aa. u ∈ L4 ⇔ ∃ v ∈ (a + b)* : u = a v aa + aa ⇔ u ∈ a (a + b)* aa + aa L4 → a (a + b)* aa + aa. EX.6 a) Un identificateur est une suite de lettres ou de chiffres commençant par une lettre. Ecrire une définition régulière. lettre = [a-zA-Z] chiffre = [0-9] ident = lettre (lettre chiffre)* b) Idem, mais en imposant que la première lettre soit une majuscule. lettre = [a-zA-Z] chiffre = [0-9] maj = [A-Z] ident_prol = maj (lettre chiffre)* c) Ecrire une définition régulière pour les nombres réels tels que: 123 54.37 0.5 21E3 32E+5. chiffre_non_nul = [1-9] chiffre = chiffre_non_nul  0 entier = chiffre_non_nul chiffre*  0 decimal = .chiffre* expt = E[+-]?entier reel = [+-]? (entier decimal?  decimal) expt? Suite de la solution (Prière de uploads/s3/ smi5-corrigetd1-compilation.pdf