Exercice mot de Dyck (théories des langages)

[e5mm100]

Bonjour j'ai un devoir à faire qui (je trouve) est super difficile et j'ai besoin d'aide pour savoir si ce que j'ai fait est correcte .
voici mon énoncé:
Partie 1:
On rappelle que pour un mot u et un symbole σ, |u| |u|σ représente le nombre d’occurrences du symbole σ dans u.
Soit Σ = {a, b}. On définit le langage de Dyck DΣ (sur Σ) par
• e ∈ DΣ
• ∀u, v ∈ Σ, u, v ∈ DΣ ⇒ aubv ∈ DΣ.
1. Soit l’application
d : Σ∗ → Z
u → |u|a − |u|b
Montrer que u appartient à DΣ si et seulement si
• d(u) = 0,
• pour tout préfixe u' de u d(u') ≥ 0.
2. Montrer que DΣ est stable par concaténation (i.e. la concaténation de deux mots de Dyck est encore un mot de Dyck).

Pour la première question voici ce que j'ai fait (on m'a aidé pour le faire ):

Montrons que Dz ⊆ Σ* par induction:
e ∈ DΣ, et ∀u, v ∈ Σ, u, v ∈ DΣ ⇒ aubv ∈ DΣ
|aubv|a=|u|a+|v|a+1=|u|b+|v|b=|aubv|b

si w' est un prefixe de aubv on a alors:

dans un premier cas w'=au' avec u' prefixe de u,
on a alors : |u'|a>=|u'|b et donc |au'|a>=|au'|b d'où |w'|a >= |w'|b

dans un second cas on a sot w'=aubv' avec v' prefixe de v:
on a alors |u'|a=|u'|b et |v'|>=|av'|b on a donc |aubv'|a >= |aubv'|b d'ou |w'|a>=|w'|b


Montrons que Σ* ⊆ Dz par récurrence:
si n =0 alors le mot est vide et e ∈ DΣ(longueur du mot )

soit n∈ N, supposons que pour tout mot ∈Σ* de longueur k<n ∈Dz.
Montrons alors que tout mot de longueur n de Σ* ∈ DΣ.

soit w ∈ DΣ avec |w|=n;
soit w' le plus petit préfixe tq |w'|a=|w'|b.Il commence forcement par a et fini par b car w'∈ DΣ . Nous avons donc |u|'a=|w'|a-1=|w'|b-1=|u'|b

Tout préfixe u'' de u' vérifie |au''|>|au''|b et donc |u''|>|u''|b. D'après ce que nous avons monter plus haut w s'écrit au'bv Montrons que v ∈ Σ*

|v|a=|v|b et |w|a=|w|b et |u|a=|u|b
si v' est un préfixe de v alors au'bv' est un préfixe de w et donc
|au'bv'|a=|au'bv'|b ce qui montre que |v'|a>=|v'|b

donc w s'écrit au'bv' avec u' et v' w'∈ Σ*. D'après l'hypothèse de rccurence u' et v sont aussi dans DZ et donc w=au'bv et est aussi dans Dz.

=>voilà ce que j'ai fait, je ne sais pas si c'est bon ou si je suis à côté de la plaque
pour la deuxième question par contre je ne sais pas par ou commencer est ce que quelqu'un peut me mettre sur la voie

[tournesol]

Nom d'un chien !

[tournesol]

J'ai un doute sur ta définition de
Je pense que c'est .........aubv appartient à

[GaBuZoMeu]

Il n'y a pas de problème quand à la définition des mots de Dyck.
Par contre la rédaction est à peu près impossible à suivre à cause de la confusion des notations entre , , qui normalement désigne le monoïde de tous les mots. Un vrai bazar !
On devine que l'idée y est, mais il faut soigneusement reprendre la rédaction.
La question 2 est une conséquence très facile de ce qui est montré en 1.

[tournesol]

Et cette stabilité par concaténation permet de caractériser par

(aub et uv appartiennent à )