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

Tags
arts langage existe alors currence exercice
Documents similaires
Explication de texte marx Explication de texte du février Chemins de la philosophie France Culture Expliquer le texte suivant Le travail est de prime abord un acte qui se passe entre l'homme et la nature L'homme y joue lui-même vis à vis de la nature le r 0 0
Aigoritm 1 1 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? Méthodologie de la dissertation ? ? ? ? ? ? ? ? ? ? ? ? ? ? CPlan de la dissertation Introduction ? Amener le sujet en une ou deux phrases ? Dé ?nir les termes clés et donner le cadre spatio- 0 0
Lucie histoire Elle rêve de la rentrée scolaire sa rentrée en première C ? est une élève timide qui n ? a pas beaucoup d ? amis elle se fait critiquer pour son style car elle n ? est pas à la mode ? et elle n ? a jamais eu de copain En gros elle est le co 0 0
artist book ARTISTS ? BOOKS DENIS OZANNE CHLOE DENIS OZANNE RUE DE PROVENCE PARIS sur rendez - vous dnozanne club- internet fr m a q u e t t e i l l u s i o n s ? c o u v e r t u r e s e r g e b i l o u s ? 0 0
Fiche 4aprise de note en franc ais i 0 0
Devoir commun de mathematiques 4eme 2011 version 1 0 0
Memoire 4 Léopold Winandy Le pouvoir d ? assimilation des élèves de solfège sur les plans du rythme de l ? intonation et de l ? ou? e musicale CLe pouvoir d ? assimilation des élèves de solfège sur les plans du rythme de l ? intonation et de l ? ou? e mus 0 0
10 23 esadse livretannee1 0 0
pdf Notion d ? algorithme et les instructions de base -Notion d ? algorithme Un algorithme est une suite d ? actions ou d ? instructions qui doivent être exécutées dans un ordre bien déterminé pour résoudre un problème ou réaliser un travail - - Caractéri 0 0
Cours fortran Université de Gharda? a Faculté des Sciences et de la Technologie Département Génie civil ère Master GC Module Complément de programmation Support de cours Fortran Année universitaire CCours Complément de programmation Mr A Bahaz PETITE INTR 0 0
  • 41
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager