Homomorphisme de monoides
-
Ddut dernière édition par
Bonjour,
Je crois ne toujours pas avoir compris la notion d'homomorphisme de monoïdes.Exemple:
Pour tout mot u sur un alphabet A, on note lg(u) la longueur de u, autrement dit le nombre de lettres dans u.1)Est-ce que f est une fonction de A∗ vers N? Non car tout élément du départ n'associe pas un élément d'arrivé.
- Est-ce que f est un homomorphisme de monoïdes de (A∗, .) vers(N,+)?
Je commence par chercher l'élément neutre:
(A*, .) est 1 monoide avec e = ε\varepsilonε or f(ε\varepsilonε)=0
Après je suis un peu perdu, je sais que je dois prouver deux égalitées.
Merci
-
Bonsoir Dut,
1)Revoie ta réponse
Pour tout mot u sur un alphabet A, on note lg(u) la longueur de u.
Donc à tout mot u de A* on associe un naturelf est donc une fonction de A* vers N
- Revois peut-être la définition de ton cours.
L'élément neutre de (A*,.) est ϵ\epsilonϵ (mot de longueur nulle)
L'élément neutre de (N,+) est 0Il faut prouver deux propriétés :
i )f(ϵ)=0f(\epsilon)=0f(ϵ)=0
ii) u et v étant deux mots quelconques de A*,
f(u.v)=f(u)+f(v)f(u.v)=f(u)+f(v)f(u.v)=f(u)+f(v)Je te laisse réfléchir pour savoir si ces deux propriétés sont vraies ou fausses.
-
Ddut dernière édition par
re bonsoir
un bout important de l'énoncé a été oublié: On définit les fonctions
f:u→lg(u) + 1Pour l'endomorphisme j'ai continué comme suit:
f(epsilon)=0 -> non car on fait quoi qu'il arrive +1u=ab
v= abcd
f(u.v)=7 alors que f(u)=3 et f(v)=5
7#8Donc ce n'est pas un homomorphisme de monoide.
Bonne soirée
-
Il aurait été mieux de donner tout l'énoncé !
Sans ta dernière précision , j'ai cru que f (u)=lg(u)
Il faut donc prendre finalement f(u)=lg(u)+1\fbox{f(u)=lg(u)+1}f(u)=lg(u)+1
Pour la 1), tu dois donc dire que, à tout mot u de A* on associe un naturel qui est la longueur du mot u à laquelle on ajoute 1
f est donc une fonction de A* vers N
(Si ce n'était pas le cas, la seconde question n'aurait pas de sens)
Pour la 2)
Pour i)
f(ϵ)=0+1=1f(\epsilon)=0+1=1 f(ϵ)=0+1=1 donc propriété i) non réaliséePour ii)
Ton exemple est bon.
Pour dire NON, un exemple suffit, donc ça va.La propriété ii) n'est pas réalisée.
f n'est donc pas un homomorphisme de monoïdes.
Je pense que tu as bien compris.
Bonne soirée à toi.
-
Ddut dernière édition par
Oui j'ai compris
Merci beaucoup bonne soirée
-
De rien !
Bon dimanche.