A potência é como uma “filtragem” das palavras por comprimento. Pense em como um conjunto de “ingredientes” (os símbolos).
Se eu quero palavras de tamanho , pego desses ingredientes e os combino de todas as formas possíveis. O número de elementos em é , onde é o tamanho do alfabeto, refletindo todas as combinações possíveis de símbolos.
Formalmente podemos explicar isso como:
Potência de um alfabeto () é dado por um alfabeto onde definimos que como o conjunto de todas as palavras de comprimento exatamente sobre , onde é um número inteiro não negativo ().
Caso especial
, onde é a palavra vazia (comprimento 0).
Se , então contém todas as sequências de símbolos escolhidos de .
Enquanto foca em palavras de um comprimento fixo, é o “universo completo” das palavras sobre . Ele junta tudo: palavras de comprimento 0 (), comprimento 1 (), comprimento 2 (), e assim por diante.
Note
Esse conjunto é infinito se tiver pelo menos um símbolo, pois podemos formar palavras arbitrariamente longas.
Ou seja, todas as sequências binárias possíveis, de qualquer tamanho.
Esse exemplo mostra como lista palavras de um tamanho específico, enquanto engloba tudo. Se quiséssemos definir uma linguagem como “todas as palavras binárias de comprimento par”, ela seria: