Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
Discussion fermée
#1 10-03-2018 18:05:12
- Edison11
- Membre
- Inscription : 11-12-2017
- Messages : 9
Ensemble défini par induction
Bonjour j'aurai besoin d'un peu d'aide concernant l'exercice suivant :
Soit ∑={(,)} l'alphabet constitué de la parenthèse ouvrante et de la parenthèse fermante. L'ensemble D ⊆ ∑* des parenthésages bien formés, appelé langage de Dyck, est défini inductivement par :
Base : {ε} (où ε représente le mot vide, c'est à dire un mot sans lettre)
Règles :
a) ∀x∈D : (x)∈D
b) ∀x.y∈D : x.y∈D (où . désigne la concaténation entre deux mots)
Écrivez tous les mots de Dyck de longueurs 0, 1, 2, 3, 4, 5 et 6. Que remarquez vous ?
Voici ce que j'ai fait :
Mot de longueur 0 : Le seul mot contenant aucune lettre est le mot vide. Or la règle a) ne nous permet pas d'écrire un mot de longueur 0.
Mot de longueur 1 : Impossible
Mot de longueur 2 : () où x et y correspondent au mot vide
Mot de longueur 3 : ((), ()) où y correspond au mot vide
Mot de longueur 4 : (()), ())( , (((),()))premier cas x = ( et y = ), deuxième cas x = ) et y = (, troisième cas x = y = (, quatrième cas x = y = )
Mot de longueur 5 : Impossible
Mot de longueur 6 : Impossible
Est-ce juste ? Merci d'avance pour votre aide!
Hors ligne
#2 11-03-2018 20:41:18
- Fred
- Administrateur
- Inscription : 26-09-2005
- Messages : 7 035
Re : Ensemble défini par induction
Bonjour
Mot de longueur 0 : Le seul mot contenant aucune lettre est le mot vide. Or la règle a) ne nous permet pas d'écrire un mot de longueur 0.
Je pense que si, le mot vide est dans ta base....
Mot de longueur 1 : Impossible
Mot de longueur 2 : () où x et y correspondent au mot vide
Il faudrait justifier qu'il n'y a aucun mot de longueur 1.
() est bien le seul mot de longueur 2, mais je ne comprends pas ta justification.
Pour prouver que () est dans ton langage, on utilise la règle a avec x qui vaut le mot vide.
Mot de longueur 3 : ((), ()) où y correspond au mot vide
Là encore, je ne comprends pas. J'essaie de t'expliquer en détails.
Un mot de longueur 3 peut être obtenu de deux façons :
1. en appliquant la règle a. qui dit que (x) est dans le langage si x est dans le langage. Mais il faudrait que x soit un mot de longueur 1 dans ton langage, et il n'y en a pas!
2. en appliquant la règle b., qui dit que xy est dans le langage si x et y le sont. Mais pour que xy soit de longueur 3, il faut nécessairement que ou x ou y soit de longueur 1, et il n'y a pas de mots de longueur 1 dans ton langage.
Peux-tu continuer???
F.
Hors ligne
Pages : 1
Discussion fermée