Diferença de linguagens regulares

Considere duas linguagens regulares L₁, L₂. Vamos demonstrar que a diferença delas, L = L₁ ∖ L₂, também é uma linguagem regular.

Ideia

Na verdade, não há muito o que demonstrar. Para a diferença de dois conjuntos vale a seguinte relação:

$$L_1\setminus L_2=L_1\cap L_2^{\prime },$$

em que L₂′ é o complemento da linguagem L₂. Pelos capítulos sobre a interseção de linguagens regulares e sobre o complemento de uma linguagem regular, sabemos que as linguagens regulares são fechadas sob essas duas operações. Isso significa que conseguimos construir um autômato que aceita a interseção de linguagens e o complemento de uma linguagem. Podemos, assim, usar esses autômatos para construir um autômato que aceitará a linguagem L₁ ∩ L₂′, que é, ao mesmo tempo, a linguagem L₁ ∖ L₂.

Exemplo

Considere este autômato A₁, que aceita todas as palavras que contêm um número par de uns:

e o autômato A₂, que aceita as palavras que contêm um número ímpar de zeros:

Construímos um autômato que aceitará a diferença dessas linguagens. Precisamos, então, de um autômato A₂′, que será o complemento do autômato A₂. Basta trocar os estados finais e não finais:

Agora só falta construir o autômato A, que aceitará a interseção das linguagens L(A₁) e L(A₂′):

Fontes

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