Interseção de linguagens regulares

Considere duas linguagens regulares L₁, L₂. Vamos demonstrar que a interseção delas, L = L₁ ∩ L₂, também é uma linguagem regular.

Ideia da demonstração

Temos duas linguagens regulares L₁ e L₂ e queremos demonstrar que a interseção delas, L₁ ∩ L₂, é de novo uma linguagem regular. Como L₁ e L₂ são linguagens regulares, existem autômatos finitos A₁ e A₂ que aceitam as linguagens L₁ e L₂, ou seja, valem L(A₁) = L₁ e L(A₂) = L₂. Nós construiremos um autômato finito A que aceitará a linguagem L₁ ∩ L₂, e com isso demonstraremos que a linguagem L₁ ∩ L₂ é regular.

Uma palavra pertence à interseção das linguagens se pertence à linguagem L₁ e, ao mesmo tempo, a L₂. Ou seja, a palavra deve ser aceita pelo autômato A₁ e, ao mesmo tempo, pelo autômato A₂. Vamos usar exatamente a mesma ideia que usamos na união de linguagens regulares, mudando apenas o conjunto dos estados finais.

Formalização do procedimento

Temos dois autômatos,

$$\begin{array}{rcl}{A}_1& =& ⟨Q_1,{\mathrm{\Sigma }}_1,{\delta }_1,q_0,F_1⟩\\ A_2& =& ⟨Q_2,{\mathrm{\Sigma }}_2,{\delta }_2,p_0,F_2⟩\end{array}$$

Construímos o autômato A = ⟨Q, Σ, δ, q, F⟩, que aceita a linguagem L(A₁) ∩ L(A₂). Vale que

• Q = Q₁ × Q₂
• Σ= Σ₁ ∩ Σ₂
• q = ⟨q₀, p₀⟩
• F = F₁ × F₂

Para a função de transição δ valerá a seguinte relação:

$$\mathrm{\forall }q\in Q_1,p\in Q_2:\delta (⟨q,p⟩,a)=⟨{\delta }_1(q,a),{\delta }_2(p,a)⟩$$

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 interseção dessas linguagens. O conjunto de estados desse autômato tem a forma Q = Q₁ × Q₂, o estado inicial é o estado ⟨q₀, p₀⟩ e os estados finais são F₁ × F₂:

Em seguida completamos as transições de modo que δ(⟨q,p⟩, a) = ⟨δ₁(q, a), δ₂(p, a)⟩:

Neste autômato, por exemplo, do estado ⟨q₀, p₀⟩ há uma transição para o símbolo 0 até o estado ⟨q₀,p₁⟩. Isso significa que o autômato A₁ tem, do estado q₀, uma transição para o símbolo 0 de volta ao estado q₀. Já o autômato A₂ tem, para o símbolo 0, uma transição do estado p₀ para o estado p₁.

Podemos testar o autômato. Ele deve aceitar palavras como 110 ou 00000 (contêm um número par de uns e, ao mesmo tempo, um número ímpar de zeros), mas não deve aceitar palavras como 11, 111, 1010.

Fontes

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