Remerciez-le!

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

corrige Chapitre option informatique Corrigé des exercices ? Mots et alphabets ? Exercice ? TOB EO RNOT T OB EAR E GU L A R R EGX ? Exercice ? 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

Chapitre option informatique Corrigé des exercices ? Mots et alphabets ? Exercice ? TOB EO RNOT T OB EAR E GU L A R R EGX ? Exercice ? 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é ?xe de u dans le second cas u est pré ?xe de v b Raisonnons par récurrence sur u ?? Si u le résultat est évident ?? Si u 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 t u p uupup ?? uvqvq ?? donc uv est pré ?xe de t De même t v q vvqvq ?? vupvq ?? donc vu est pré ?xe de t 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 ? a La relation est ré exive si on pose x u et y on a u xy yx donc uR u La relation est symétrique pour des raisons évidentes La relation est transitive supposons uR v et vR w 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 uR w b Si on a uR v il su ?t 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 uR v c Si uR v il existe x et y tel que u xy et v yx Alors un xy xy n ?? et vn yx n ?? yx xy n ?? xy donc unRvn Réciproquement on raisonne par récurrence sur n ?? N ? ?? Si n le résultat est évident ?? Si n supposons le résultat acquis jusqu ? au rang n ?? et considérons x et