Ensemble défini par induction

[invite20527e22]

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!
-----

[Médiat]

Bonsoir,

Mot de longueur 3 : ((), ()) où y correspond au mot vide

Vous penser vraiment que (() est bien formé ? Si oui, comment l'obtenez-vous ?

Pour 6, que pensez-vous de (())() et il y en a d'autres ...

[invite23cdddab]

Et je ne vois pas en quoi la règle 1) empêche de considérer le mot vide.

J'aurai même tendance à considérer que comme il est dans la base, il fait par définition partie du langage.

Sinon, c'est assez facile de prouver par induction que :
- tout les mots sont de longueur paire
- quelque soit l'entier n, il existe au moins un mot de longueur 2n

[invite20527e22]

Effectivement je me suis trompé j'avais mal compris, je reprends :

Mot de longueur 0 : ε

Quel(s) mot(s) peut-on former à partir de ε ? () et ε

On a donc :

Mot de longueur 1 : il n'y en a pas
Mot de longueur 2 : ()

Quel(s) mot(s) peut-on former à partir des mots précédents ? (()), ()(), (), ε

On a donc :

Mot de longueur 3 : il n'y en a pas.
Mot de longueur 4 : (()) et ()()

Quel(s) mot(s) peut-on former à partir des mots précédents ? ((())), (()()), (())(), ()(()), ()()(), (()), ()(), (), ε

On a donc :

Mot de longueur 5 : il n'y en a pas.
Mot de longueur 6 : ((())), (()()), (())(), ()(()) et ()()()

Bilan il n'existe que des mots de longueur paire

[A voir en vidéo sur Futura]