Monoide livre

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Em álgebra abstrata, o monoide livre sobre um conjunto A é o monoide cujos elementos são todas as strings (ou sequências de caracteres) finitas formadas por zero ou mais elementos de A. Ele é normalmente denotado por A. O elemento de identidade é a única sequência com zero elementos, muitas vezes chamada de string vazia e denotada por ε ou λ, e a operação do monoide é a concatenação de strings. O semigrupo livre em A é o subsemigrupo de A contendo todos os elementos exceto a string vazia. Ele é denotado geralmente por A+.

Exemplos[editar | editar código-fonte]

O monoide (N,+) dos números naturais (incluindo o zero) com a operação de adição é um monoide livre sobre um único gerador (isto é, de posto 1). O único gerador livre é o número 1.

Por exemplo, se A = {a, b, c} os elementos de A são da forma

{ε, a, ab, ba, caa, cccbabbc,...}

Se A é um conjunto, a função comprimento da palavra em A é o único homomorfismo de monoide de A em N que leva cada elemento de A em 1.