Conversão AFN AFD

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Merge-arrows 2.svg
Foi proposta a fusão deste artigo ou se(c)ção com Construção do conjunto das partes. Por favor crie o espaço de discussão sobre essa fusão e justifique o motivo aqui; não é necessário criar o espaço em ambas as páginas, crie-o somente uma vez. Perceba que para casos antigos é provável que já haja uma discussão acontecendo na página de discussão de um dos artigos. Verifique ambas (1, 2) e não se esqueça de levar toda a discussão quando levar o caso para a central. (desde outubro de 2013)

Se tivermos um e-AFN M2 <Q2 ,Σ, q2,0 , δ2 , A2 > que reconhece uma linguagem L. Então um AFD M 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[editar | editar código-fonte]