Homomorphisme de monoides


  • D

    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é.

    1. 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


  • mtschoon

    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 naturel

    f est donc une fonction de A* vers N

    1. 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 0

    Il 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.


  • D

    re bonsoir
    un bout important de l'énoncé a été oublié: On définit les fonctions
    f:u→lg(u) + 1

    Pour l'endomorphisme j'ai continué comme suit:
    f(epsilon)=0 -> non car on fait quoi qu'il arrive +1

    u=ab
    v= abcd
    f(u.v)=7 alors que f(u)=3 et f(v)=5
    7#8

    Donc ce n'est pas un homomorphisme de monoide.

    Bonne soirée


  • mtschoon

    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ée

    Pour 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.


  • D

    Oui j'ai compris 🙂
    Merci beaucoup bonne soirée


  • mtschoon

    De rien !

    Bon dimanche.


Se connecter pour répondre