União de linguagens regulares

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

Procedimento com um autômato determinístico

Ideia do procedimento

Temos duas linguagens regulares L₁ e L₂ e queremos demonstrar que a uniã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.

Como faremos isso? Temos à mão os autômatos finitos A₁ e A₂, que aceitam cada uma das linguagens. Podemos dizer que a palavra w pertence à linguagem L₁ ∪ L₂ se, e somente se, pelo menos um dos autômatos A₁ ou A₂ a aceita.

O autômato A poderia funcionar assim: para a entrada w, ele vai simular a computação do autômato A₁ para a entrada w. Se A₁ aceitar a palavra w, então A também aceita a palavra w. Se A₁ rejeitar a palavra w, então A ainda tenta simular a computação de A₂ para a entrada w. Se A₂ aceitar a palavra w, então A também aceita a palavra w. Caso contrário, rejeita.

Resta-nos formalizar o que significa que o autômato A “simula” a computação de outro autômato.

Formalização

Temos duas linguagens regulares L₁ e L₂, que são aceitas pelos autômatos finitos

$\begin{array}{rcl} A_{1} & = & ⟨ Q_{1}, Σ_{1}, δ_{1}, q_{1}, F_{1} ⟩ \\ A_{2} & = & ⟨ Q_{2}, Σ_{2}, δ_{2}, q_{2}, F_{2} ⟩ . \end{array}$

Construímos o autômato finito A = ⟨Q, Σ, δ, q, F⟩, que aceitará a linguagem L = L₁ ∪ L₂. Vamos usar a ideia de simular os dois autômatos A₁, A₂. Imaginemos, então, que temos na entrada a palavra w = w₁w₂… w_n e que agora vamos simular ao mesmo tempo o andamento dos autômatos A₁ e A₂ para a palavra w. A configuração inicial do autômato A₁ é ⟨q₁, w₁w₂… w_n⟩, e a configuração inicial de A₂ é ⟨q₂, w₁w₂… w_n⟩. Em cada autômato fazemos agora um passo de computação, e com isso chegamos às configurações ⟨δ₁(q₁, w₁), w₂… w_n⟩ e ⟨δ₂(q₂, w₁), w₂… w_n⟩.

Vemos que essas configurações diferem apenas na primeira componente; a segunda — a parte não lida da palavra — é sempre a mesma. Durante a simulação, portanto, não precisamos manter duas configurações de dois autômatos, basta-nos uma configuração da forma ⟨⟨q_i, q_j⟩, w_l… w_n⟩, em que q_i ∈ Q₁ e q_j ∈ Q₂. Em outras palavras, o nosso autômato A, que estamos construindo, terá a configuração inicial ⟨⟨q₁, q₂⟩, w⟩. A primeira parte do par ⟨q₁, q₂⟩ representa o estado em que o autômato A₁ se encontra no momento, e a segunda componente representa o estado atual do autômato A₂.

Podemos escrever, assim, que o autômato A, que estamos construindo, terá o conjunto de estados igual a Q = Q₁ × Q₂. Será o produto cartesiano dos estados dos dois autômatos anteriores. A ideia seguinte é que o autômato A terá o estado inicial ⟨q₁, q₂⟩ e, se o autômato A₁ passar com o símbolo w₁ para o estado q_i e o autômato A₂ passar com o símbolo w₁ para o estado q_j, então o autômato A passará com o símbolo w₁ para o estado ⟨q_i, q_j⟩.

Escrevemos a função de transição δ assim (aqui já supomos que estamos no momento nos estados q_i e q_j):

$δ (⟨ q_{i}, q_{j} ⟩, w) = ⟨ δ_{1} (q_{i}, w), δ_{2} (q_{j}, w) ⟩$

Resta resolver apenas pequenos detalhes. Para o alfabeto vale Σ= Σ₁ ∪ Σ₂. O estado inicial é igual a q = ⟨q₁, q₂⟩. E os estados finais são todos os pares ⟨q_i, q_j⟩ tais que q_i ∈ F₁ ou q_j ∈ F₂.

Ilustração do procedimento

Considere dois autômatos. O primeiro é o autômato A₁, que aceita todas as palavras (incluindo a palavra vazia) em que se alternam zeros e uns, isto é, palavras da forma 01, 0101, 010101, …

O outro autômato, A₂, aceita as palavras que contêm pelo menos um zero:

A união dessas linguagens é formada pelas palavras que contêm um zero ou são da forma 01, 0101, … Agora construímos o autômato finito A = ⟨Q, Σ, δ, q, F⟩, que aceitará exatamente essa linguagem união. Primeiro vamos mostrar como serão os estados desse novo autômato A. Será o produto cartesiano dos estados do primeiro e do segundo autômato:

$Q = Q_{1} \times Q_{2} = {⟨ q_{0}, p_{0} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{0} ⟩, ⟨ q_{2}, p_{1} ⟩}$

Assim são os seis estados do autômato A, que aceita a linguagem união L(A₁) ∪ L(A₂). No diagrama ficariam assim:

Não se assuste por termos estados compostos de pares de estados — isso serve apenas para nos orientarmos melhor sobre o que de fato acontece no autômato. Os estados poderiam muito bem se chamar, de maneira usual, q₀, …, q₅. Os estados finais são aqueles que contêm o estado q₀ ou p₁, que são os estados finais dos autômatos originais. O estado inicial é ⟨q₀, p₀⟩.

Agora precisamos encontrar todas as transições. Escrevemos uma tabela assim:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

E vamos completando a tabela aos poucos. Primeiro descobrimos para onde levará a transição do estado ⟨q₀, p₀⟩ com a entrada 0. Descobrimos para onde vai a transição do estado q₀ com a entrada 0 no autômato A₁: ela vai para o estado q₁. No autômato A₂, a transição de p₀ com zero vai para o estado p₁. Então escrevemos na tabela ⟨q₁, p₁⟩:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Com a entrada 1 obtemos: para o autômato A₁ temos δ₁(q₀, 1) = q₂ e para o autômato A₂ temos δ₂(p₀, 1) = p₀. Obtemos, assim, o estado ⟨q₂, p₀⟩.

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ \end{array}$

Completamos o resto da tabela:

$\begin{array}{ccc} 0 & 1 \\ ⟨ q_{0}, p_{0} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{0}, p_{1} ⟩ & ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \\ ⟨ q_{1}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{0} ⟩ \\ ⟨ q_{1}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{0}, p_{1} ⟩ \\ ⟨ q_{2}, p_{0} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{0} ⟩ \\ ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ & ⟨ q_{2}, p_{1} ⟩ \end{array}$

E, de acordo com essa tabela, só falta desenhar o resto do diagrama.

Podemos testar se o autômato funciona como deve. Vamos tentar aceitar a palavra 0100. O autômato percorrerá, sucessivamente, os estados

$⟨ q_{0}, p_{0} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{0}, p_{1} ⟩, ⟨ q_{1}, p_{1} ⟩, ⟨ q_{2}, p_{1} ⟩$

Como o estado ⟨q₂, p₁⟩ é um estado final, o autômato A aceita a palavra 0100. Como seria se tentássemos aceitar a palavra 0100 com os autômatos A₁ e A₂? O autômato A₁ percorreria, sucessivamente, estes estados:

$q_{0}, q_{1}, q_{0}, q_{1}, q_{2}$

O autômato terminou no estado q₂, que não é final, então o autômato A₁ não aceitaria essa palavra. E o autômato A₂?

$p_{0}, p_{1}, p_{1}, p_{1}, p_{1}$

O estado p₁ é final, então o autômato A₂ aceitaria a palavra 0100. Observe que os autômatos A₁ e A₂ terminaram nos estados q₂ e p₁, o que está de acordo com o fato de o autômato A ter terminado no estado ⟨q₂, p₁⟩.

Procedimento com um autômato não determinístico

Exemplo

Podemos demonstrar que o conjunto das linguagens regulares é fechado sob a união também construindo um autômato não determinístico, que será muito mais simples.

Temos, assim, duas linguagens regulares L₁, L₂ e queremos demonstrar que a união delas, L = L₁ ∪ L₂, também é uma linguagem regular. Como L₁, L₂ são linguagens regulares, devem existir autômatos A₁, A₂ que aceitam essas linguagens. Ou seja, valem L(A₁) = L₁ e L(A₂) = L₂. Com esses autômatos construímos o autômato A, que aceitará a linguagem L, isto é, L(A) = L.

Suponha que os autômatos finitos A₁ e A₂ sejam assim:

Construiríamos o autômato que aceitaria a união das duas linguagens criando um novo estado inicial e levando, desse estado, duas transições ε para os estados iniciais originais. Só isso. O autômato ficaria assim:

Formalização

Temos dois autômatos A₁ = ⟨Q₁, Σ, δ₁, q₁, F₁⟩ e A₂ = ⟨Q₂, Σ, δ₂, q₂, F₂⟩. Construímos o autômato A = ⟨Q, Σ, δ, q₀, F⟩, que aceitará a união das linguagens aceitas pelos autômatos anteriores, isto é, L(A) = L(A₁) ∪ L(A₂). Nesse caso, valem:

Q = Q₁ ∪ Q₂ ∪ {q₀}
F = F₁ ∪ F₂

E definimos a função de transição δ assim:

$δ (q, a) = {\begin{cases} δ_{1} (q, a) & se & q \in Q_{1} \\ δ_{2} (q, a) & se & q \in Q_{2} \\ {q_{1}, q_{2}} & se & q = q_{0} \land a = ε \\ \emptyset & se & q = q_{0} \land a \neq ε \end{cases}$

Fontes

Capítulos: Fechamento das linguagens regulares, União de linguagens regulares, Interseção de linguagens regulares, Diferença de linguagens regulares, Complemento de uma linguagem regular, Concatenação de linguagens regulares, Fecho de uma linguagem regular

« Anterior: Propriedades de fecho das linguagens regulares

Próximo: Interseção de linguagens regulares »