Discussion :

[St-42-FCM-57]

Bonjour,

Je ne sais pas si je suis au bon endroit pour poser ce genre de question, auquel cas je m'en excuse.
Je suis tombé sur des annales de Théorie des Langages, il y avait cette question :
" Soit L un langage sur l'alphabet {a,b}. Est-il exact que L⁺ est toujours égal à L⁺⁺ ? "

Alors j'ai cherché, mais je ne sais pas comment prouver. Je sais que c'est vrai, car dans un cours j'ai trouvé que (L⁺ )⁺ = L⁺, mais pour le démontrer, je ne vois pas comment faire... A noter que L⁺ correspond à l'itération stricte.

Quelqu'un aurait-il des éléments pour m'aider ?

Merci d'avance, et bonne journée !

[valentin03]

Par la logique: Des procédures poursuivant le même but sont égales ?

[St-42-FCM-57]

Je ne vois pas trop où tu veux en venir ?
Peut-être en prouvant la double inclusion, mais je ne vois pas comment et par où commencer.

[Flodelarab]

Bonjour

Si le "plus" en exposant signifie bien que tu enlèves le mot vide (de longueur nulle) de ton ensemble de mots formés à partir de ton alphabet de base, alors tu peux l'enlever 1 fois, 2 fois ou 100 fois, c'est pareil.

L⁺ = L⁺⁺ = L⁺⁺⁺ = L^++++++++++++

[edit]Et même si tu considères ta composition de mots comme un nouvel alphabet de base. Seul la composition de mots de longueur nulle peut donner un mot de longueur nulle. Or, il n'y en a pas. [/edit]

[St-42-FCM-57]

Bonjour,

Merci pour la contribution
Oui c'est vrai ce que tu dis.
Mais par exemple si mon langage contient les mots "a" et "b" seulement.
Alors L⁺ sera {a,b,aa,ab,bb,aaa,abaa,...}, et dans ce cas, quel sera (L⁺)⁺ ? Ça sera le même ?

[Flodelarab]

Ça sera le même ?

Et oui. C'est le sens de l'égalité.

quel sera (L+)+ ?

Ça, c'est toi qui peut le dire en fonction de ton énoncé.

• Si le "plus" en exposant signifie \ L⁰, alors tu peux empiler des "+" puisque l'ensemble L⁰ a déjà été enlevé.
  
• Si le "plus" en exposant signifie "on prend l'ensemble comme ensemble de départ et on combine, puis on enlève le mot vide", alors on combine des mots de longueur supérieure à 0, ce qui ne peut donner 0.
  Quand à la combinaison, comme l'alphabet qui permet de créer L⁺ est contenu dans L⁺, recombiner pour obtenir L⁺⁺ donnera la même chose. Il n'y a pas de caractéristique spéciale obtenue par le fait de combiner 2 fois.
  
  C'est comme dénombrer les nombres entiers et les nombres pairs. Il y en a le même nombre: l'infini.
  Pourtant, on aimerait qu'il y ait 2 fois plus de nombres entiers que de nombres pairs.
  Ici, c'est pareil. Ton alphabet 2 fois combiné donne la même chose qu'une fois combiné.
  
  Reste à comprendre : (L⁴)⁴
  Ce n'est pas égal à L⁴.
  BABA est du second et BABABABABABABABA du premier, a mon avis.