Palavras são combinações dos símbolos do alfabeto. O conjunto é gerado pela operação de concatenação: se e , então .
A palavra vazia é um caso especial, pois atua como o elemento neutro da concatenação ().
Formalmente, uma palavra é um elemento do conjunto (Conjunto de todas as palavras), onde representa todas as palavras possíveis sobre , incluindo a palavra vazia, denotada por (com comprimento 0).
Notação: Se , então inclui .
Note
O conjunto está relacionado ao conceito de powerset, pois é gerado considerando todas as combinações possíveis dos símbolos do alfabeto, variando também o comprimento das palavras.