Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(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

Edison11 a écrit :

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

Pied de page des forums