Conversão AFN AFD

Se tivermos um e-AFN M2 <Q2 ,Σ, q2,0 , δ2 , A2 > que reconhece uma linguagem L. Então um AFD M <Q ,Σ, q0 , δ , A > que satisfaz as seguintes condições reconhece L :

Q = 2^Q2, ou seja o conjunto de todos os subconjuntos de Q2 q0 = {q2,0}, ou seja o conjunto de todos os estados alcançáveis a partir do estado inicial de Q2 viajando através de conexões e mais o próprio q20.

δ(q,a) = U (p e q) δ(p,a), pra cada estado q em Q, e cada simbolo a em Σ e

A = { q pertence Q | q inter A2 ≠ vazio}

É dado um algoritmo para a obtenção de um AFD a partir de um AFN:

Lembrando que um AFD, é quando uma saide de uma estado, vai para um outro estado. E um AFN, é quando a saída de uma estado vai para vários estados.

Inicialmente Q ≠ vazio

Primeiro coloque {q2,0} em Q. {q2,0} será o estado inicial do AFD M Então pra cada estado q em Q faça : Add o conjunto http://www.cs.odu.edu/~toida/nerzic/390teched/symbols/cup-delta-q.gif, onde δ aqui é o do AFN M2, como um estado para Q se ele já não o estiver lá para cada símbolo a em Σ Para esse novo estado, add δ( q, a ) = http://www.cs.odu.edu/~toida/nerzic/390teched/symbols/cup-delta-q.gif para δ de M, onde o segundo δ é do AFN M2.

Quando não há mais novos estados que possam ser adicionados pra Q, o processo termina. Todos os estados de Q, que contém estados de aceitação de M2 são estados de aceitação de M.

Bibliografia

• http://www.cs.odu.edu/~toida/nerzic/390teched/regular/fa/nfa-2-dfa.html.
• Michael Sipser, Introduction to the Theory of Computation. PWS, Boston. 1997.