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.
