06 · Equivalência entre AFD e AFND

Resumo em 30 segundos

Teorema: se um AFND aceita $L$ , existe um AFD que aceita $L$ . A prova é construtiva (construção de subconjuntos): cada estado do AFD é um conjunto de estados do AFND, o conjunto dos estados “ativos” naquele momento. A transição do AFD é a união das transições do AFND. Estados finais do AFD são os conjuntos que contêm algum final do AFND.

Anterior: 05 - Autômatos Finitos Não Determinísticos · Voltar ao mapa · Próxima: 07 - Equivalência AF e GR

Slide 3: o teorema

Se $L$ é aceita por um AFND, então existe um AFD que aceita $L$ .

Consequência: o AFND não é mais poderoso que o AFD. É uma representação mais livre, mais fácil de escrever, com o mesmo poder. A volta é trivial: todo AFD já é um AFND (cada conjunto de destinos tem um elemento só).

Slides 4 e 5: a construção

Dado o AFND $M = (K, V_{t}, T, i, F)$ , define-se o AFD $M^{'} = (K^{'}, V_{t}, T^{'}, [i], F^{'})$ :

Componente do AFD	Definição
$K^{'}$	subconjuntos de $K$ ; o estado $[q_{i}, \dots, q_{j}]$ representa o conjunto ${q_{i}, \dots, q_{j}}$
$T^{'}$	$T^{'} ([q_{i}, \dots, q_{j}], a) = [q_{k}, \dots, q_{l}]$ sse $T (q_{i}, a) \cup \dots \cup T (q_{j}, a) = {q_{k}, \dots, q_{l}}$
inicial	$[i]$ , o conjunto só com o inicial do AFND
$F^{'}$	subconjuntos que contêm pelo menos um estado de $F$

Detalhe no slide 4

O slide escreve $T^{'} : K^{'} \times V_{t} \to 2^{K^{'}}$ . Como $M^{'}$ é determinístico, o correto é $T^{'} : K^{'} \times V_{t} \to K^{'}$ . Cada estado de $K^{'}$ já é um conjunto de estados do AFND, então o destino é um único elemento de $K^{'}$ , não um conjunto deles.

Slide 6: a prova, em português

Por indução no tamanho da palavra $w$ , mostra-se:

$\hat{T}^{'} ([q_{0}], w) = [q_{i}, \dots, q_{j}] ⟺ \hat{T} (q_{0}, w) = {q_{i}, \dots, q_{j}}$

Ou seja, o estado do AFD depois de ler $w$ é exatamente o conjunto de estados em que o AFND pode estar depois de ler $w$ .

Base ( $∣ w ∣ = 0$ , $w = ε$ ): o AFD está em $[q_{0}]$ e o AFND em ${q_{0}}$ . Iguais por definição.
Hipótese: vale para palavras de tamanho $n$ .
Passo ( $w^{'} a$ , tamanho $n + 1$ ): pela hipótese, depois de $w^{'}$ os dois estão em " ${q_{i} .. q_{j}}$ ". Lendo $a$ , o AFND vai para $T ({q_{i} .. q_{j}}, a)$ e o AFD, por definição de $T^{'}$ , vai para o mesmo conjunto.

Daí: o AFD aceita $w$ ⟺ o conjunto final contém um estado de $F$ ⟺ o AFND aceita $w$ .

Slide 7: o algoritmo

flowchart TD
  A["Comece com o estado [i]"] --> B{Há estado do AFD<br/>ainda não analisado?}
  B -- não --> Z[Fim: marque como finais<br/>os que contêm algum estado de F]
  B -- sim --> C[Pegue um estado S = conjunto]
  C --> D["Para cada símbolo a:<br/>destino = união de T(q,a) para q em S"]
  D --> E{Destino já existe<br/>na tabela?}
  E -- sim --> B
  E -- não --> F[Crie o novo estado<br/>e coloque na fila] --> B

Dica de prova: só crie os subconjuntos que aparecem a partir de $[i]$ . Não precisa listar os $2^{∣ K ∣}$ subconjuntos; os inalcançáveis podem ser ignorados.

Slides 8 a 10: exemplo resolvido

AFND:

T	0	1
→ q0	{q1}	{q2}
q1	{q0, q1}	{q0}
* q2	{q0}	{q2}

Passo a passo:

$[q_{0}]$ : com 0 vai para $[q_{1}]$ ; com 1 vai para $[q_{2}]$ . Dois estados novos.
$[q_{1}]$ : com 0, $T (q_{1}, 0) = {q_{0}, q_{1}}$ , estado novo $[q_{0} q_{1}]$ ; com 1, $[q_{0}]$ .
$[q_{2}]$ : com 0, $[q_{0}]$ ; com 1, $[q_{2}]$ .
$[q_{0} q_{1}]$ : com 0, ${q_{1}} \cup {q_{0}, q_{1}} = [q_{0} q_{1}]$ ; com 1, ${q_{2}} \cup {q_{0}} = [q_{0} q_{2}]$ , novo.
$[q_{0} q_{2}]$ : com 0, ${q_{1}} \cup {q_{0}} = [q_{0} q_{1}]$ ; com 1, ${q_{2}} \cup {q_{2}} = [q_{2}]$ .
Nenhum estado novo: fim.

AFD resultante (idêntico ao do slide 10, conferido por programa):

T	0	1
→ [q0]	[q1]	[q2]
[q1]	[q0q1]	[q0]
* [q2]	[q0]	[q2]
[q0q1]	[q0q1]	[q0q2]
* [q0q2]	[q0q1]	[q2]

Finais: $[q_{2}]$ e $[q_{0} q_{2}]$ , os que contêm $q_{2}$ . Conferi também que o AFD e o AFND aceitam exatamente as mesmas palavras até tamanho 10.

Slide 11: exercícios

Exercício 1: AFND com alfabeto {a, b, c}

T a b c
→ q0 {q0, q1} {q1} {q2}
q1 {q0} {q0, q2} {q0}
* q2 {q1} {q0, q1} {q2}

AFD equivalente (6 estados alcançáveis):

T a b c
→ [q0] [q0q1] [q1] [q2]
[q0q1] [q0q1] [q0q1q2] [q0q2]
[q1] [q0] [q0q2] [q0]
* [q2] [q1] [q0q1] [q2]
* [q0q1q2] [q0q1] [q0q1q2] [q0q2]
* [q0q2] [q0q1] [q0q1] [q2]

Exemplo de conta: $[q_{0} q_{2}]$ com b $= T (q_{0}, b) \cup T (q_{2}, b) = {q_{1}} \cup {q_{0}, q_{1}} = [q_{0} q_{1}]$ .

Conferido por programa: mesma linguagem do AFND até tamanho 7.

T	a	b	c
→ q0	{q0, q1}	{q1}	{q2}
q1	{q0}	{q0, q2}	{q0}
* q2	{q1}	{q0, q1}	{q2}

T	a	b	c
→ [q0]	[q0q1]	[q1]	[q2]
[q0q1]	[q0q1]	[q0q1q2]	[q0q2]
[q1]	[q0]	[q0q2]	[q0]
* [q2]	[q1]	[q0q1]	[q2]
* [q0q1q2]	[q0q1]	[q0q1q2]	[q0q2]
* [q0q2]	[q0q1]	[q0q1]	[q2]

Exercício 2: AFND do diagrama com p0 a p3

Lendo o diagrama ampliado: $p_{0} 0 p_{1}$ , $p_{0} 1 p_{2}$ ; $p_{1}$ com laço em 1, $p_{1} 1 p_{0}$ , $p_{1} 0 p_{3}$ ; $p_{2}$ com laço em 0, $p_{2} 0 p_{1}$ , $p_{2} 1 p_{3}$ ; $p_{3}$ final e sem saídas.

T 0 1
→ p0 {p1} {p2}
p1 {p3} {p0, p1}
p2 {p1, p2} {p3}
* p3 ∅ ∅

AFD equivalente (11 estados alcançáveis, mais o estado vazio ∅):

T 0 1
→ [p0] [p1] [p2]
[p1] [p3] [p0p1]
[p2] [p1p2] [p3]
* [p3] ∅ ∅
[p0p1] [p1p3] [p0p1p2]
[p1p2] [p1p2p3] [p0p1p3]
* [p1p3] [p3] [p0p1]
[p0p1p2] [p1p2p3] [p0p1p2p3]
* [p1p2p3] [p1p2p3] [p0p1p3]
* [p0p1p3] [p1p3] [p0p1p2]
* [p0p1p2p3] [p1p2p3] [p0p1p2p3]

O conjunto vazio ∅ funciona como estado poço (não final, laço em 0 e 1). O diagrama omite ele para não poluir. Na prova, inclua ∅ se o professor exigir função de transição total.

Conferido por programa: mesma linguagem do AFND até tamanho 10. Como o diagrama do slide é pequeno, confira a direção da seta entre p1 e p2 no seu PDF; eu li como $p_{2} 0 p_{1}$ .

T	0	1
→ p0	{p1}	{p2}
p1	{p3}	{p0, p1}
p2	{p1, p2}	{p3}
* p3	∅	∅

T	0	1
→ [p0]	[p1]	[p2]
[p1]	[p3]	[p0p1]
[p2]	[p1p2]	[p3]
* [p3]	∅	∅
[p0p1]	[p1p3]	[p0p1p2]
[p1p2]	[p1p2p3]	[p0p1p3]
* [p1p3]	[p3]	[p0p1]
[p0p1p2]	[p1p2p3]	[p0p1p2p3]
* [p1p2p3]	[p1p2p3]	[p0p1p3]
* [p0p1p3]	[p1p3]	[p0p1p2]
* [p0p1p2p3]	[p1p2p3]	[p0p1p2p3]

Aprofundamento com os livros

Páginas das edições da sua pasta: Menezes 3ª edição (2000) e Ramos, José Neto e Vega (Bookman).

O teorema no Menezes (Teorema 2.7, p. 43)

É a mesma construção dos slides, com dois detalhes que o livro deixa explícitos:

Os estados do AFD são combinações sem repetição dos estados do AFND, e a ordem não importa: $[q_{0} q_{1}]$ e $[q_{1} q_{0}]$ são o mesmo estado.
A volta (todo AFD é um AFND) “decorre trivialmente das definições”, porque um AFD é um AFND em que todo conjunto de destinos tem um elemento só.

A prova é por indução no tamanho da palavra, igual à do slide 6: o estado do AFD depois de ler $w$ é exatamente o conjunto de estados em que o AFND pode estar.

Exemplo do livro: “termina em aaa” (Menezes, Exemplos 6 e 7, p. 42 a 44)

O AFND tem 4 estados (veja o diagrama na aula 05). Aplicando a construção a partir de $[q_{0}]$ (conferi por programa):

T	a	b
→ $[q_{0}]$	$[q_{0} q_{1}]$	$[q_{0}]$
$[q_{0} q_{1}]$	$[q_{0} q_{1} q_{2}]$	$[q_{0}]$
$[q_{0} q_{1} q_{2}]$	$[q_{0} q_{1} q_{2} q_{f}]$	$[q_{0}]$
* $[q_{0} q_{1} q_{2} q_{f}]$	$[q_{0} q_{1} q_{2} q_{f}]$	$[q_{0}]$

De 16 subconjuntos possíveis, só 4 são alcançáveis. O livro chama esses estados de $p_{0}, p_{1}, p_{2}, p_{f}$ : cada um conta quantos a seguidos acabaram de aparecer. Ler b sempre volta para o começo.

O algoritmo do Ramos é um pouco diferente (Algoritmo 3.4, p. 160 a 162)

Em vez de começar do estado inicial e só criar os conjuntos alcançáveis (como nos slides e no Menezes), o Ramos parte da tabela inteira do AFND e vai trocando cada transição não determinística por um estado novo que junta os destinos, copiando para ele as transições dos estados que o compõem. Repete até não sobrar não determinismo. Consequências que ele destaca:

podem sobrar estados inacessíveis no final (no Exemplo 3.15, p. 162, o estado original $q_{1}$ fica inacessível), que depois podem ser removidos;
o número de estados do AFD fica limitado por $2^{∣ Q ∣} - 1$ (todas as combinações não vazias), e o Exemplo 3.17 (p. 164) mostra um caso em que as $2^{3} - 1 = 7$ combinações aparecem.

Os dois métodos chegam a autômatos equivalentes. O dos slides costuma dar menos trabalho na prova porque nunca cria estado inalcançável.

O caminho contrário é trivial

O Ramos mostra (Exemplo 3.18, p. 166) que dá para transformar qualquer AFD num AFND equivalente só acrescentando um estado “morto” alcançável por um símbolo que já tinha transição. A linguagem não muda. Ou seja, a equivalência é mesmo nos dois sentidos.

Depois da conversão, minimize

A construção de subconjuntos costuma gerar estados equivalentes (que se comportam igual para qualquer palavra). No AFND do slide 9 da aula 05, por exemplo, a conversão gera 5 estados, mas dois deles podem ser fundidos. O algoritmo de minimização do Menezes está explicado, com esse exemplo, em 08 - Tópicos Complementares dos Livros. Já os dois exercícios desta aula e o exemplo dos slides 8 a 10 não diminuem: conferi por programa que os AFDs obtidos já são mínimos.

Para aprofundar nos livros

Onde ler (páginas das edições da sua pasta)

Menezes (3ª ed.): Teorema 2.7 e Exemplo 7, p. 43 e 44; 2.8 Minimização, p. 66 a 72; exercícios 2.8 e 2.25a, p. 81 e 84.

Ramos, José Neto e Vega: Teorema 3.3 e Algoritmo 3.4, p. 160 a 167; 3.7 Minimização de Autômatos Finitos, p. 216 a 230.

Relacionadas: 05 - Autômatos Finitos Não Determinísticos · 07 - Equivalência AF e GR · Glossário · Flashcards

tags	lfa, automatos, afd, afnd, construcao-de-subconjuntos
aliases	Equivalência AFD AFND, Construção de subconjuntos, Determinização

Linguagens Formais e Autômatos

Explorador

06 - Equivalência AFD e AFND

06 · Equivalência entre AFD e AFND

Slide 3: o teorema

Slides 4 e 5: a construção

Slide 6: a prova, em português

Slide 7: o algoritmo

Slides 8 a 10: exemplo resolvido

Slide 11: exercícios

Aprofundamento com os livros

O teorema no Menezes (Teorema 2.7, p. 43)

Exemplo do livro: “termina em aaa” (Menezes, Exemplos 6 e 7, p. 42 a 44)

O algoritmo do Ramos é um pouco diferente (Algoritmo 3.4, p. 160 a 162)

Depois da conversão, minimize

Para aprofundar nos livros

Visão de gráfico

Sumário

Backlinks