Conversão de AFN em AFD

Vamos mostrar como converter um autômato não determinístico em um autômato determinístico, o que demonstrará que o poder computacional dos autômatos não determinísticos e o dos determinísticos são equivalentes.

Ideia básica

Considere um autômato não determinístico ⟨Q_N, Σ_N, δ_N, q₀, F_N⟩ sem transições ε. Montamos o autômato determinístico ⟨Q_D, Σ_D, δ_D, p₀, F_D⟩ de modo que

Q_D ⊆ 2^Q_N
Σ_D = Σ_N
p₀ = {q₀}
F_D = {Q ∈ Q_D | Q ∩ F_N ≠ ∅}

Definimos a função de transição δ_D da seguinte maneira:

$\forall Q \in Q_{D}, a \in Σ_{D} : δ_{D} (Q, a) = ⋃_{q \in Q} δ_{N} (q, a)$

O que isso significa? O autômato não determinístico pode estar ao mesmo tempo em vários estados, de modo que, por exemplo, podemos chegar a uma situação em que o nosso autômato não determinístico está nos estados {q₀, q₁}. Ao ler o símbolo seguinte, por exemplo 1, podemos chegar ao conjunto de estados {q₀, q₂, q₃}. Na versão determinística do mesmo autômato, isso se manifesta assim: criamos dois estados, damos a eles os nomes {q₀, q₁} e {q₀, q₂, q₃} e introduzimos entre eles uma transição para o símbolo 1. Formalmente, passamos de um estado para outro, mas, graças aos nomes, saberemos que no autômato não determinístico estaríamos em dois ou, respectivamente, em três estados.

Exemplo

Considere este autômato não determinístico:

Para construir o autômato determinístico, precisamos antes de tudo construir uma nova função de transição. Para isso, usamos uma tabela, na qual anotamos todas as transições. No começo, a tabela é assim:

$\begin{array}{ccc} estado / símbolo & 0 & 1 \\ {q_{0}} \end{array}$

Na coluna da esquerda teremos, no fim do algoritmo, todos os estados do autômato determinístico. A tabela preenchida determinará, então, a função de transição. Agora anotamos na tabela para quais estados vamos se estamos no estado {q₀} e na entrada estão os símbolos 0 e 1.

$\begin{array}{ccc} estado / símbolo & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

Do estado q₀ sai, para o símbolo 0, uma transição apenas para o estado q₁, enquanto para o símbolo 1 saem transições para os estados q₁ e q₂. Agora acrescentamos à tabela dois novos estados: {q₁} e {q₁, q₂}. Por quê? Sempre que escrevemos na tabela algum conjunto de estados que ainda não temos na coluna da esquerda, nós o acrescentamos a essa coluna.

$\begin{array}{ccc} estado / símbolo & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} \\ {q_{1}, q_{2}} \end{array}$

e de novo preenchemos. No caso do estado {q₁, q₂} não podemos esquecer de verificar os dois estados, isto é, fazer a união dos estados aonde vamos a partir do estado q₁ com os estados aonde vamos a partir do estado q₂.

Obtivemos vários estados novos, que precisamos acrescentar à tabela:

…e de novo completamos as transições:

$\begin{array}{ccc} estado / símbolo & 0 & 1 \\ {q_{0}} & {q_{1}} & {q_{1}, q_{2}} \\ {q_{1}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{1}, q_{2}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{3}} \\ {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{3}} & {q_{0}, q_{1}, q_{2}, q_{3}} \\ {q_{0}, q_{3}} & {q_{1}} & {q_{1}, q_{2}} \end{array}$

Os estados {q₀, q₁, q₃}, {q₁} e {q₁,q₂} já estão ali, então acrescentamos apenas o estado {q₀,q₁,q₂,q₃}.

Não acrescentamos mais nenhum estado novo, então a tabela está preenchida. Agora só falta montar o diagrama. Os estados do autômato determinístico estão na primeira coluna, e as transições para os símbolos 0 e 1 estão nas colunas seguintes. Todo estado que contém algum estado final do autômato original será um estado final também neste autômato. Ou seja, todo estado que contém q₃ será um estado final. O autômato ficará assim:

Podemos mostrar que o autômato funciona mesmo corretamente. Vamos tentar aceitar a palavra 11001. No autômato determinístico seguiremos o caminho

$q_{0} \to^{1} q_{1}, q_{2} \to^{1} q_{0}, q_{3} \to^{0} q_{1} \to^{0} q_{0}, q_{1}, q_{3} \to^{1} q_{0}, q_{1}, q_{2}, q_{3}$

e o autômato aceitaria a palavra, porque o último estado {q₀, q₁, q₂, q₃} é final. No autômato não determinístico, durante a simulação chegaríamos aos mesmos estados, isto é, começaríamos no estado q₀ e, para o símbolo 1, chegaríamos aos estados {q₁, q₂}. O símbolo 1 seguinte nos levaria aos estados {q₀,q₃} etc. para os demais estados. No fim nos encontraríamos em todos os estados {q₀, q₁, q₂, q₃}, e o autômato aceitaria a palavra.

Fontes

Capítulos: Autômato finito, Autômato completo, Autômato finito não determinístico, Simulação de um autômato não determinístico, Conversão de AFN em AFD

« Anterior: Simulação de um autômato não determinístico

Próximo: Minimização de autômatos »