Chapitre 3 option informatique Corrigé des exercices • Mots et alphabets   

Chapitre 3 option informatique Corrigé des exercices • Mots et alphabets    Exercice 1 T O B E O R N O T T O B E A R E G U L A R R E G X    Exercice 2 a) Par hypothèse il existe des mots x et y tels que w = ux = vy. D’après le lemme de Levi il existe un mot t tel que u = vt, y = tx ou v = ut, x = ty. Dans le premier cas v est préfixe de u ; dans le second cas u est préfixe de v. b) Raisonnons par récurrence sur |u|. – Si u = ε le résultat est évident. – Si |u| ⩾1, supposons le résultat acquis pour tout mot de longueur inférieure, et appliquons le lemme de Levi : il existe un mot t tel que u = at et u = tb. On a donc at = tb et |t| < |u| donc par hypothèse de récurrence a = b et t ∈{a}∗. Mais alors u = at ∈{a}∗, ce qui prouve le résultat souhaité. c) Posons t = up = vq. On a t2 = u2p = uupup−1 = uvqvq−1 donc uv est préfixe de t2. De même, t2 = v2q = vvqvq−1 = vupvq−1 donc vu est préfixe de t2. Or uv et vu ont même longueur donc uv = vu. D’après le deuxième théorème issu du lemme de Levi il existe un mot w et deux entiers m et n tels que u = wm et v = wn.    Exercice 3 a) La relation est réflexive : si on pose x = u et y = ε on a u = xy = yx donc uRu. La relation est symétrique pour des raisons évidentes. La relation est transitive : supposons uRv et vRw. Il existe donc x,y,z,t ∈Σ∗tels que u = xy, v = yx, v = zt, w = tz. On a yx = zt donc d’après le lemme de Levi il existe un mot r tel que y = zr, t = rx ou alors z = yr, x = rt. Dans le premier cas on a u = (xz)r et w = r(xz) ; dans le second cas on a u = r(ty) et w = (ty)r. Dans les deux cas on a bien uRw. b) Si on a uRv il suffit de poser w = x pour avoir uw = xyx = wv. Réciproquement, s’il existe w tel que uw = wv d’après le premier théorème issu du lemme de Levi il existe deux mots x et y et un entier k tel que u = xy, v = yx (et w = (xy)kx) donc on a bien uRv. c) Si uRv il existe x et y tel que u = xy et v = yx. Alors un = (xy)(xy)n−1 et vn = (yx)n−1(yx) = (xy)n−1(xy) donc unRvn. Réciproquement, on raisonne par récurrence sur n ∈N∗. – Si n = 1 le résultat est évident. – Si n > 1, supposons le résultat acquis jusqu’au rang n −1, et considérons x et y tels que un = xy et vn = yx. Observons déjà que |x| + |y| = n|u| = n|v| donc |u| = |v|. Puisque n > 1 l’un des deux mots x ou y est de longueur supérieure à u ; supposons par exemple que ce soit x. Jean-Pierre Becirspahic 3.2 option informatique x est préfixe de un donc il existe k ⩾1 et u′ préfixe de u tel que x = uku′. Puisque |v| = |u| il existe v′ suffixe de v tel que x = v′vk. On a uku′ = v′vk donc |v′| = |u′| ⩽|u| ; v′ est donc préfixe de u et par voie de conséquence v′ = u′. Ainsi, uku′ = u′vk ce qui, d’après la question précédente, prouve que ukRvk. Par hypothèse de récurrence on en déduit que uRv.    Exercice 4 a) Soit n ⩾3. Il est facile d’établir par récurrence que si n est pair, f4 est suffixe de fn et que si n est impair, f3 est suffixe de fn. Or f3 = ba et f4 = bab donc le résultat est vrai pour tout n ⩾3. b) Montrons par récurrence sur n ⩾3 que gn est un palindrome. – Si n = 3, g3 = ε est un palindrome. – Si n = 4, g4 = b est un palindrome. – Si n = 5, g5 = bab est un palindrome. – Si n ⩾6, supposons le résultat acquis jusqu’au rang n −1 et distinguons deux cas selon la parité de n. Si n est pair, fn = fn−1fn−2 = fn−2fn−3fn−2 = gn−2abgn−3bagn−2ab donc gn = gn−2abgn−3bagn−2. Par hypothèse de récurrence gn−2 et gn−3 sont des palindromes, donc il en est de même de gn. Si n est impair on obtient gn = gn−2bagn−3abgn−2 et le raisonnement est identique.    Exercice 5 a) On détermine si un mot appartient à D en calculant sa valuation ainsi que celle de ses préfixes. let dick = let rec aux acc = function | [] −> acc = 0 | a::q −> acc >= 0 && aux (acc+1) q | b::q −> acc >= 0 && aux (acc−1) q in aux 0 ;; b) Soit m = m1m2 ···mp ∈D , et ϕ(1), ϕ(2), . . ., ϕ(k + 1) = p les valeurs de j pour lesquelles σ(m1m2 ···mj) = 0. Alors (m1 ···mϕ(1)), (mϕ(1)+1 ···mϕ(2)), . . ., (mϕ(k)+1 ···mp) sont les facteurs de m. Ainsi, déterminer le nombre de facteurs revient à dénombrer le nombre de préfixes p de m de valuation nulle : let nb_facteurs m = let rec aux acc nb = function | [] −> nb | b::q when acc=1 −> aux 0 (nb+1) q | b::q −> aux (acc−1) nb q | a::q −> aux (acc+1) nb q in aux 0 0 m ;; (On part du principe que cette fonction n’est utilisée que sur les mots de D .) Pour obtenir la fonction d’affichage, on remplace le comptage par des effets de bord dans la fonction précédente : let factorisation m = let rec aux acc = function | [] −> () | [b] −> print_char ‘)‘ | b::q when acc=1 −> print_string ")." ; aux 0 q | b::q −> print_char ‘)‘ ; aux (acc−1) q | a::q −> print_char ‘(‘ ; aux (acc+1) q in aux 0 m ;; Illustration : # factorisation [a;a;b;b;a;b;a;a;b;a;b;b] ;; ( ( ) ) . ( ) . ( ( ) ( ) ) − : u n i t = ( ) Corrigé des exercices 3.3    Exercice 6 a) Nous avons successivement : aababa = ababab = bababb = abaabb = bababb = aababb = bababb. Montrons par récurrence sur |r| que rs = s r. – C’est évident si r = ε. – Si |r| > 1, on suppose le résultat acquis pour tout mot de longueur inférieure, et on considère deux cas : – si r = ar′, alors rs = r′sb = sr′b = sar′ = s r ; – si r = br′, alors rs = r′sa = sr′a = sbr′ = s r. b) Concrètement, il faut remplacer des a par des b (et réciproquement) puis prendre l’image miroir du mot. On utilise un fold left : let invert = function | a −> b | b −> a ;; let barre = it_list (fun q t −> (invert t)::q) [] ;; Illustration : # barre [a;a;b;a;b;a] ;; − : alphabet l i s t = [ b ; a ; b ; a ; b ; b ] c) On observe que un+1 = unaun, ce qui conduit à la définition : let rec pliage = function | 0 −> [] | n −> let u = pliage (n−1) in u@(a::(barre u)) ;; d) On peut commencer par observer que |un+1| = 2|un| + 1, donc |un| = 2n −1. Montrons par récurrence sur n que les lettres d’indice 4p +1 de un sont des a et les lettres d’indices 4p +3 des b : – c’est clair lorsque n ⩽2 car u0 = ε, u1 = a et u2 = aab ; – si n ⩾2, supposons que un s’écrive un = aw2bw4aw6 ···aw2kb (il se termine par un b car 2n −1 ≡3 mod 4). Alors : un+1 = aw2bw4aw6 ···aw2kbaaw2kbw2k−2a···aw2b ce qui établit le résultat au rang n + 1. On peut en outre noter que si on considère le mot vn formé des lettres d’indices pairs de un, à savoir vn = w2w4 ···w2k alors vn+1 = vnavn. Sachant que v1 = ε, on en déduit par récurrence que vn = un−1 pour n ⩾1, et donc que pour tout n ∈N, w2n = wn. Tout ceci nous permet d’obtenir la fonction de calcul de la ne lettre suivante : let rec uploads/s3/ 03-corrige.pdf

Tags
Administrationpréfixe langage alors existe récurrence
Documents similaires
  • 31
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager