Maths discrète, alphabet langage ...

[architecte]

Bonjour à tous.
Je comprend les notations V+ ou V* lorsque V est un alphabet. En revanche, si V est un langage je suis perdu !

Imaginons le langage L = {a, b, c}. Que vaudrait L+ et L* ?

Je vous remercie d'avance.

[Ben314]

Salut,
Tu peut rappeller ce que signifie pour toi (ou ton prof) les notations V+ et V* dans le cas d'un alphabet ?

[Doraki]

V* est l'ensemble des mots qui sont obtenus en concaténant des mots de V (0 ou plus), avec la possibilité de concaténer 0 mots pour faire le mot vide.

V+ est l'ensemble des mots qui sont obtenus en concaténant des mots de V (1 ou plus).

[architecte]

Alors,
V+ -> l'ensemble des mots de longueur au moins 1 que l'on peut écrire sur l'alphabet V
V* -> V+ incluant le mot vide.

Maintenant, voici les définitions que j'ai si L correspond à un langage :
L+ est l'ensemble des concaténations d'un nombre quelconque (y compris 0) de mots de L

L* est l'ensemble des concaténations d'un nombre quelconque non nul de mots de L

Voila. Si vous comprenez ma question pourriez vous me répondre avec un exemple ?

Cordialement

[architecte]

Doraki, si je comprend bien :

Soit L le langage {a, b, c}
L* = {motVide, a, b, c, ab, ac, ba, bc, ca, cb, abc, bac, cba};

L+ = L* sans motVide;

[Doraki]

Je pense que tu (ou alors ton prof) as inversé tes définitions de L+ et L*.

Et puis tu as le droit d'utiliser plusieurs fois le même mot dans la concaténation.

Si L = {a,b,c},
la concaténation de L avec lui-même donne :
LL = {a,b,c}{a,b,c} = {aa,ab,ac,ba,bb,bc,ca,cb,cc}

L*= {vide} + L + LL + LLL + ...
= {vide,a,b,c,aa,ab,ac,ba,bb,bc,ca,cb,cc,aaa,aab,aac ...} est infini.

L+ = L + LL + LLL + ... = L(L*)

Si L lui-même contient le mot vide, alors il n'y a pas de différence entre L+ et L*.