2.3 Equivalência entre AFDs e AFNs
Dois autômatos X e Y são equivalentes sse (se e somente se) ambos reconhecem a mes-
ma linguagem, ou seja, sse L(X) = L(Y).
Vamos mostrar, nesta aula, que os modelos AFN e AFD são equivalentes, ou seja, va-
mos mostrar que as duas afirmações abaixo são verdadeiras:
- Todo AFD tem um AFN equivalente – trivial, porque o modelo AFN estende o
AFD, então todo AFD pode ser tratado como um AFN.
- Todo AFN tem um AFD equivalente – mostraremos como converter a seguir!
Veremos a conversão de AFN para AFD em duas partes:
1. Conversão de AFN sem transição vazia (ε) para AFD
2. Conversão de AFN qualquer para AFD
De AFN sem Transição ε para AFD – Descrição Formal
editarA conversão que veremos é a aplicação de técnica conhecida como construção de sub-
conjuntos. A idéia chave dessa conversão é tratar um conjunto de estados do AFN como
um estado individual do AFD convertido.
Digamos que {q0,q3,q4} seja um conjunto de estados de um AFN. Na conversão, vamos
tratá-lo como um único estado do AFD convertido. Para diferenciar, vou chamar isto de
um estado-conjunto do AFD.
Um estado-conjunto do AFD convertido representa a situação em que o AFN poderia
estar nos vários estados representados, depois de ler a mesma cadeia de símbolos (ao
seguir por caminhos diferentes).
- Exemplo: se no AFN, lendo a cadeia “aa”, existir dois (ou mais) caminhos que
levam aos estados q1 ou q3; no novo AFD, após ler “aa”, o resultado será o estado-
conjunto {q1,q3}.
Segue a descrição formal da conversão. Como ponto de partida, considere o AFN N
sem transição ε definido assim:
N = (Q, Σ, δ, q0, Qaceita)
editarPodemos converter N para um AFD D equivalente assim:
D = (QD, Σ, δD, q0-D, Qaceita-D) , onde:
editarQD conterá todos os possíveis subconjuntos de Q. Em outras palavras, QD é o con-
junto das partes de Q.
(Explicação: cada estado-conjunto de D será algum conjunto de estados do autô-
mato N. Apesar da definição acima, nem todo subconjunto de Q será um estado ú-
til no novo autômato – alguns estados serão impossíveis de atingir. Na próxima
seção, veremos como encontrar somente os estados úteis).
Σ é o alfabeto (igual ao do AFD).
q0-D = {q0}
(Explicação: o estado-conjunto inicial será o conjunto unitário formado pelo esta-
do inicial do autômato original N. Porque, em N, antes de ler qualquer símbolo,
esta é a única situação possível).
Qaceita-D = { X | X é um estado-conjunto que contém algum estado de Qaceita }
(Explicação: Os estados de aceitação X do autômato D serão aqueles estados-
conjuntos que possuírem algum estado de aceitação do autômato N. Porque isso
tal estado-conjunto X representa que há algum caminho em N que termina em es-
tado de aceitação).
δD será definida para cada estado-conjunto R (que pertence a QD) e para cada sím-
bolo ai da seguinte forma:
(Explicação: Para cada estado q ∈ R, aplica a transição do AFN para o símbolo ai,
obtendo um conjunto de estados de destino; o resultado é a união de todos estes
conjuntos para todo q ∈ R).
Na próxima seção, vamos ver uma maneira bem mais prática de calcular um AFD a partir
de um dado AFN.
De AFN sem Transição ε para AFD – Descrição Informal
editarSegue um roteiro prático que você pode seguir para fazer a conversão de um AFN para
um AFD:
1. Calcule o estado inicial do novo autômato – ele será simplesmente o conjunto
unitário formado com o estado inicial do AFN.
2. Depois, faça a tabela que representa a função de transição δD do AFD. As li-
nhas serão os estados-conjuntos, enquanto as colunas serão os símbolos. Para
descobrir os estados-conjunto úteis, vamos preencher a tabela inicialmente uma
única linha, que é a do estado-conjunto inicial (do passo 1) e, posteriormente,
adicionaremos novas linhas toda vez que um novo estado for calculado (no pró-
ximo passo).
3. Para cada estado-conjunto R do AFD (linha da tabela) e cada símbolo ai
(colu-na) fazer isso:
- Para cada estado do AFN (autômato original) que compõe o conjunto R,
calcule as transições para o símbolo ai.
- Coloque na tabela um só conjunto com todos os estados obtidos. Este será
um estado-conjunto útil (atingível) do AFD.
- Se o estado-conjunto obtido não tiver aparecido antes, crie uma nova linha
com esse novo estado.
4. O processo acima (passo 3) encerra quando todas as transições para estados-
conjuntos úteis conhecidos estiverem calculadas e não surgir mais nenhum novo
estado-conjunto.
5. Por fim, identifique os estados de aceitação -- basta haver um estado de aceita-
ção do AFN dentro do estado-conjunto do AFD.
6. Desenhe o autômato, se necessário (ou se quiser).
Exemplo 1 (AFN sem transição ε):
