Répondre à la discussion
Affichage des résultats 1 à 4 sur 4

Ensemble défini par induction

  1. #1
    Edison11

    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!

    -----


  2. Publicité
  3. #2
    Médiat

    Re : Ensemble défini par induction

    Bonsoir,

    Citation Envoyé par Edison11 Voir le message

    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 ...
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    Tryss2

    Re : Ensemble défini par induction

    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

  5. #4
    Edison11

    Re : Ensemble défini par induction

    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

Discussions similaires

  1. Quelle est la proportion d'un ensemble de nombre dans l'ensemble des Réels?
    Par Youri Gagarine dans le forum Mathématiques du supérieur
    Réponses: 4
    Dernier message: 30/07/2017, 14h07
  2. Suite défini par U0>=0 TS
    Par franite dans le forum Mathématiques du collège et du lycée
    Réponses: 10
    Dernier message: 30/10/2015, 21h51
  3. Différence continu et défini
    Par Tobouktou dans le forum Mathématiques du collège et du lycée
    Réponses: 7
    Dernier message: 25/07/2010, 14h04
  4. Suite défini par une intégrale.
    Par neokiller007 dans le forum Mathématiques du collège et du lycée
    Réponses: 11
    Dernier message: 16/03/2008, 19h28