Operação de complemento em linguagens

---

O complemento de uma linguagem $L_1$ em relação a ${\Sigma }^{\ast }$ é o conjunto de todas as palavras possíveis sobre $\Sigma$ que não estão em $L_1$.

Formalmente:

$${\Sigma }^{\ast }-L_1=\{x\in {\Sigma }^{\ast }\mid x\notin L_1\}$$

Exemplo

Se $\Sigma =\{a,b\}$ e $L_1=\{a,ab\}$, o complemento inclui todas as palavras em ${\Sigma }^{\ast }$ (como $ϵ,b,aa,ba,bb,aba,\dots$) exceto $a$ e $ab$.

Como ${\Sigma }^{\ast }$ é infinito, o complemento também será infinito, exceto pelos elementos excluídos de $L_1$.

Referências

---

Aula 2 - Alfabetos palavras e linguagens