Operação de potenciação em linguagens

---

As potências de uma linguagem $L$ são definidas recursivamente com base na concatenação:

• $L^0=\{ϵ\}$, onde $ϵ$ é a palavra vazia (elemento neutro da concatenação);
• $L^{n+1}=L\cdot L^n$, para todo inteiro $n\ge 0$.

Isso significa que $L^n$ representa a concatenação de $L$ consigo mesma $n$ vezes.

Exemplo

Se $L=\{ab,aab\}$:

• $L^0=\{ϵ\}$ (a palavra vazia, por definição);
• $L^1=L=\{ab,aab\}$ (uma cópia da linguagem original);
• $L^2=L\cdot L=\{abab,abaab,aabab,aabaab\}$, pois:
  • $ab\cdot ab=abab$,
  • $ab\cdot aab=abaab$,
  • $aab\cdot ab=aabab$,
  • $aab\cdot aab=aabaab$.

As potências são usadas para gerar palavras de comprimentos variados a partir de uma linguagem base.

Referências

---

Aula 2 - Alfabetos palavras e linguagens