Conversão de autômato em expressão regular

Vamos mostrar como converter qualquer autômato finito em uma expressão regular.

Descrição do algoritmo

Na entrada temos algum AFN A. Primeiro fazemos dele um AFNG. Na segunda fase, em cada passo eliminamos um estado, alteramos corretamente a função de transição e repetimos, até que sobrem apenas dois estados — o inicial e o final. Entre eles haverá uma aresta que terá como rótulo uma expressão regular, que será o resultado do algoritmo inteiro. O procedimento todo consiste, portanto, principalmente em eliminar um estado e depois corrigir o autômato, de modo a obtermos um autômato equivalente.

Eliminação de um estado

Podemos ilustrar como eliminar um estado com um exemplo simples. Suponha que uma parte do nosso autômato seja assim:

em que R_i são algumas expressões regulares. Como ficaria o autômato se eliminássemos o estado q_r? Podemos imaginar que estamos no estado q_i e nos perguntamos: que palavras somos capazes de gerar neste trecho? Se formos do estado q_i diretamente para o estado q_j, serão todas as palavras que correspondem à expressão regular R₄.

Mas, se formos para o estado q_r, podemos gerar palavras da forma R₁. No estado q_r, porém, podemos ficar em laço pela expressão regular R₂, de modo que, na verdade, podemos gerar palavras da forma $R_1\circ (R_2^{\ast })$. E, como ainda podemos chegar do estado q_r ao estado q_j, acrescentamos ali ainda a expressão regular R₃. No total, por esse caminho, podemos obter palavras da forma $R_1\circ (R_2^{\ast })\circ R_3$.

Agora sabemos que dessa parte do autômato podem surgir palavras da forma R₄ ou da forma $R_1\circ (R_2^{\ast })\circ R_3$. É claro que podemos escrever isso na forma de expressão regular como $(R_4)|(R_1\circ (R_2^{\ast })\circ R_3)$.

Agora podemos simplesmente eliminar o estado q_r, deixar apenas os dois estados q_i e q_j e, no lugar de R₄, escrever a expressão regular que acabamos de calcular:

Realizamos esse procedimento com cada aresta de cada estado q_i para algum estado q_j, inclusive os laços, isto é, inclusive o caso em que q_i = q_j.

Depois de eliminar um estado, obtemos um autômato equivalente — um autômato que reconhece a mesma linguagem.

O algoritmo completo

Na entrada temos o AFN A = ⟨Q, Σ, δ, q₀, F⟩.

1. Convertemos o AFN A em um AFNG Z = ⟨Q′, Σ, δ′, q₀′, q_f′⟩. Daqui em diante, vamos denotar pela letra k o número de estados em Z.
2. Se k = 2, o algoritmo termina e, na aresta entre o estado inicial e o final, está a expressão regular resultante.
3. Se k>2, escolhemos um estado qualquer q_r que seja diferente do estado inicial e do final, isto é, q_r ≠ q₀′ e q_r ≠ q_f′. Em seguida criamos um novo AFNG Z′ = ⟨Q′′, Σ, δ′′,q₀′,q_f′⟩, para o qual valerá: $$Q^{\prime \prime }=Q^{\prime }\setminus \left\{q_r\right\}$$ e, para todos os q_i ∈ Q′′ ∖ {q_f′} e para todos os q_j ∈ Q′′ ∖ {q₀′}, seja $${\delta }^{\prime \prime }(q_i,q_j)=(R_4)|(R_1(R_2^{\ast })R_3),$$ em que R₁ = δ′(q_i,q_r), R₂ = δ′(q_r,q_r), R₃ = δ′(q_r, q_j), R₄ = δ′(q_i, q_j). Em seguida, voltamos ao passo 2.

Exemplo

Considere na entrada este autômato finito:

Primeiro o convertemos em AFNG (não vamos representar as transições ∅ desnecessárias):

Agora aplicamos a segunda parte do algoritmo e eliminamos algum nó. Começamos pelo nó q₂. Eliminamos o nó q₂ e acrescentamos uma transição do estado q₁ para o estado q_f. Rotulamos essa transição como b(a|b)^∗, porque do nó q₁ chegamos ao estado q₂ com palavras da forma b, depois podemos ficar em laço com a|b, obtendo assim (a|b)^∗, e por fim passamos para q_f pela regra ε. Nesse caso vale b(a|b)^∗ϵ = b(a|b)^∗. Obtemos o autômato:

Resta eliminar o último estado, q₁. Acrescentamos uma aresta do estado q_s para o estado q_f. Como a rotulamos? Chegamos ao estado q₁ pela regra ε, que podemos omitir de imediato. Depois podemos ficar em laço com a, de modo que obtemos a expressão regular a^∗. E, por fim, pela aresta chegamos a q_f, então concatenamos ainda a expressão com b(a|b)^∗. A aresta será, assim, descrita pela expressão regular a^∗ b(a|b)^∗.

O autômato já tem apenas dois estados, então o algoritmo termina. Na aresta está a expressão regular resultante.

Fontes

• O exemplo e a descrição do algoritmo vêm de M. Sipser: Introduction to the Theory of Computation