Monoide livre

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

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.