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

A 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)

Podemos converter N para um AFD D equivalente assim:

D = (QD, Σ, δD, q0-D, Qaceita-D) , onde:

QD 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

Segue 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 ε):