Complemento de uma linguagem regular

Temos uma linguagem regular L. Vamos demonstrar que o complemento da linguagem L é de novo uma linguagem regular.

O que é o complemento

Por complemento da linguagem L entendemos todas as palavras que não estão na linguagem L. O complemento é denotado por L'. Ou seja, para o alfabeto Σ vale que:

$$L^{\prime }=\{w\in {\mathrm{\Sigma }}^{\ast }|w\notin L\}.$$

Por exemplo, para a linguagem das palavras que contêm pelo menos um símbolo 1, o complemento seria a linguagem que contém as palavras que não contêm nenhum símbolo 1.

Procedimento

O procedimento é muito simples. Temos uma linguagem regular L e um autômato completo determinístico A = ⟨Q, Σ, δ, q₀, F⟩ que a aceita (todo autômato finito pode ser convertido em um assim). Construímos o autômato A', que aceita L', trocando os estados finais e não finais: A' = ⟨Q, Σ, δ, q₀, Q ∖ F⟩. Só isso.

Exemplo

Considere este autômato:

O autômato que aceita o complemento da linguagem ficaria assim:

Fontes

• M. Sipser: Introduction to the Theory of Computation
• Aho, Sethi, Ullman: Compilers: Principles, Techniques, and Tools