Autômatos Finitos Não-Determinísticos

•

UFERSA

0

Hugo Dionizio Santos

07.12.2016

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

AUTÔMATOS FINITOS NÃO-
DETERMINÍSTICOS 
Marcelo Guerra 
AULA PASSADA 
 Proponha AFDs que aceitem as linguagens a 
seguir: 
 Todas as cadeias sobre Σ = {0,1} que terminem 
em 01. 
 
q0 q1 q2 
0 1 
1 0 
q1 q0 q2 
início 0 1 
0,1 
AULA PASSADA 
 Autômato Determinístico: existe apenas um 
estado para o qual ele pode transitar a partir do 
estado atual, dada uma certa entrada. 
 
 Não-determinístico: pode se encontrar em vários 
estados ao mesmo tempo. 
 
q0 q1 q2 
0 1 
1 0 
q1 q0 q2 
0 1 
0,1 
INTRODUÇÃO 
 Um AFN (ou NFA) pode assumir vários estados 
ao mesmo tempo. 
 
 AFN’s aceitam as mesmas linguagens dos AFD’s: 
porém são mais sucintos e fáceis de projetar. 
 
 É possível converter um AFN em um AFD. 
DEFINIÇÃO DE AFN 
 Um AFN A = (Q, Σ, δ, q0, F) é definido por: 
 
 Q - Um conjunto finito de estados 
 
 Σ - Um conjunto finito de símbolos de entrada 
 
 q0 ∈ Q - o estado inicial 
 
 F ⊆ Q - um conjunto de estados finais ou de 
aceitação 
 
 δ(q,a) - Uma função de transição que toma um 
estado e um símbolo de entrada e retorna um 
subconjunto de Q 
EXEMPLO 
 Aceita todos e somente as strings que terminam em 01 
 
 Podemos pensar no autômato como estando em q0 (e talvez 
entre outros estados) sempre que ele ainda não tiver 
“adivinhado” que o 01 final começou. 
 
 Se o próximo símbolo lido for zero, o estado q0 pode tentar 
capturar o possível 01 final ou fazer uma transição para si 
próprio. 
q1 q0 q2 
início 0 1 
0,1 
EXEMPLO 
 Há dois arcos rotulados com 0 saindo do estado 
inicial 
 
 No estado q1 o AFN verifica se a próxima entrada 
é 1 e passa a q2 que aceita a entrada 
 
 Não há arco rotulado com zero saindo de q1, e não 
há transições a partir de q2 – o autômato “morre” 
nesses casos 
 
REPRESENTAÇÕES 
 Assim como para os AFD’s, os AFN’s podem ser 
representados por diagramas ou por tabelas de 
transição. 
 
 
 
 
 
 
 Note que: δ(q0,0) = {q0,q1} 
0 1 
→q0 {q0, q1} {q0} 
q1 ∅ {q2} 
*q2 ∅ ∅ 
FUNÇÃO DE TRANSIÇÃO ESTENDIDA 
 δ*(q,w) retorna o conjunto de estados onde o autômato se 
encontra após processar a cadeia w. 
 
 A definição indutiva é dada por: 
 Base: δ*(q, ε) = {q} 
 
 Indução: suponha w=xa, onde a é o último símbolo de w. 
 
Suponha que δ*(q, x) = {p1, p2,…,pk}, 
 seja 
 
 
 
 então δ*(q, w) = {r1,r2,…,rm}. 
 
FUNÇÃO DE TRANSIÇÃO ESTENDIDA 
 Exemplo: Computação da cadeia 00101. 
 
 δ*(q0, ε) = {q0 } 
 
 δ*(q0, 0) = δ(δ*(q0, ε),0) = δ(q0, 0) = {q0 , q1 } 
 
 δ*(q0, 00) = δ(q0, 0)  δ(q1, 0) = {q0,q1 }   = {q0,q1 } 
 
 δ*(q0, 001) = δ(q0, 1)  δ(q1, 1) = {q0}  {q2} = {q0,q2 } 
 
 δ*(q0, 0010) = δ(q0, 0)  δ(q2, 0) = {q0,q1}   = {q0,q1} 
 
 δ*(q0, 00101) = δ(q0, 1)  δ(q1, 1) = {q0}  {q2} = {q0,q2} 
q1 q0 q2 
início 0 1 
0,1 
A LINGUAGEM DE UM AFN 
 Um AFN aceita uma string se após a leitura dos 
seus caracteres ele se encontra em algum estado 
de aceitação. 
 
 Seja A = (Q, Σ, δ, q0, F), então 
L(A) = {w | δ*(q0, w) ∩ F ≠ ∅} 
 
 O fato do autômato estar simultaneamente em outros 
estados não finais para alguma sub-cadeia da entrada 
não influencia na aceitação da palavra. 
EQUIVALÊNCIA ENTRE AFD E AFN 
EQUIVALÊNCIA ENTRE AFD E AFN 
 Há linguagens que são bem mais fáceis de 
descrever usando AFN’s 
 
 Porém, os AFD’s tem exatamente a mesma 
capacidade de reconhecimento 
 
 Na prática, um AFD tem quase o mesmo número 
de estados do AFN correspondente 
 
 No pior caso, o AFD poderá ter 2n estados em 
comparação com o menor AFN que teria n 
estados para reconhecer a mesma L 
EQUIVALÊNCIA ENTRE AFD E AFN 
 A prova da equivalência se baseia na chamada 
construção de subconjuntos, que inclui a 
construção de todos os subconjuntos de estados 
do AFN 
 
 A construção se dá partindo de um 
 AFN N = (QN, Σ, δN, q0, FN) 
 
para gerar o 
 AFD D = (QD, Σ, δD, {q0}, FD) tal que L(N) = L(D) 
EQUIVALÊNCIA ENTRE AFD E AFN 
 QD é o conjunto dos subconjuntos de QN (conjunto potência). 
Se QN tem n estados, QD tem 2
n estados. 
 Nem todos os estados são acessíveis a partir do estado inicial, 
podendo ser descartados. Assim, o número de estados de D 
pode ser efetivamente menor que 2n. 
 
 FD é o conjunto dos subconjuntos S de QN tais que 
S ∩ FN ≠ ∅ 
 
 Para cada conjunto S ⊆ QN e para cada símbolo de entrada 
a ∈ Σ, 
 
 
 
 Examinamos todos os estados p ∈ S, vemos para quais estados 
N vai a partir de p sobre a entrada a e fazemos a união de 
todos esses estados. 
EXEMPLO 
 Transformar o AFN abaixo em um AFD 
q1 q0 q2 
Início 0 1 
0,1 
0 1 
→q0 {q0, q1} {q0} 
q1 ∅ {q2} 
*q2 ∅ ∅ 
AVALIAÇÃO OCIOSA 
 Precisamos eliminar os estados inalcançáveis na 
construção dos subconjuntos. 
 
 Base: o conjunto unitário contendo o estado inicial é 
sempre alcançável 
 
 Indução: Se o conjunto S de estados é acessível, então 
para cada símbolo a, calcule o conjunto δD(S,a), que 
também serão acessíveis 
 
 
EXEMPLO 
dD({q0}, 0) = {q0, q1} e dD({q0}, 1) = {q0} 
 
0 1 
∅ ∅ ∅ 
→{q0} {q0 , q1} {q0} 
{q1} ∅ {q2} 
*{q2} ∅ ∅ 
{q0 , q1} {q0 , q1} {q0, q2} 
*{q0, q2} {q0 , q1} {q0} 
dD({q0, q1}, 0) = dN(q0, 0)  dN(q1, 0) 
= {q0, q1}   = {q0, q1} 
δD({q0, q1},1) = δN(q0,1) ∪ δN(q1,1) 
= {q0} ∪ { q2} = {q0, q2} 
 
 
dD({q0, q2}, 0) = dN(q0, 0)  dN(q2, 0) 
= {q0, q1}   = {q0, q1} 
δD({q0, q2},1) = δN(q0,1) ∪ δN(q2,1) 
= {q0} ∪  = {q0} 
 
 
AVALIAÇÃO OCIOSA 
q1 q0 q2 
Início 0 1 
0,1 
{q0, q1} {q0} {q0, q2} 
Início 0 1 
1 0 
0 
1 
AFN 
AFD 
EXERCÍCIO 
 Converta o seguinte NFA em um DFA: 
 
 
 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
q p s 
Início 0 
0,1 
r 
0,1 0 
1,0 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r},
0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
dD({p,q,s}, 0) = {p,q,r,s} 
dD({p,q,s}, 1) = {p,r,s} 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
dD({p,q,s}, 0) = {p,q,r,s} 
dD({p,q,s}, 1) = {p,r,s} 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
dD({p,q,s}, 0) = {p,q,r,s} 
dD({p,q,s}, 1) = {p,r,s} 
 
dD({p,r,s}, 0) = {p,q,s} 
dD({p,r,s}, 1) = {p,s} 
 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
dD({p,q,s}, 0) = {p,q,r,s} 
dD({p,q,s}, 1) = {p,r,s} 
 
dD({p,r,s}, 0) = {p,q,s} 
dD({p,r,s}, 1) = {p,s} 
 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
dD({p,q,s}, 0) = {p,q,r,s} 
dD({p,q,s}, 1) = {p,r,s} 
 
dD({p,r,s}, 0) = {p,q,s} 
dD({p,r,s}, 1) = {p,s} 
 
dD({p,s}, 0) = {p,q,s} 
dD({p,s}, 1) = {p,s} 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
dD({p}, 0) = {p, q} 
dD({p}, 1) = {p} 
 
dD({p,q}, 0) = dN(p,0) U dN(q,0) = {p,q} U {r} = {p,q,r} 
dD({p,q}, 1) = dN(p,1) U dN(q,1) = {p} U {r} = {p,r} 
 
dD({p,q,r}, 0) = {p,q,r,s} 
dD({p,q,r}, 1) = {p,r} 
 
dD({p,r}, 0) = {p,q,s} 
dD({p,r}, 1) = {p} 
 
dD({p,q,r,s}, 0) = {p,q,r,s} 
dD({p,q,r,s}, 1) = {p,r,s} 
 
dD({p,q,s}, 0) = {p,q,r,s} 
dD({p,q,s}, 1) = {p,r,s} 
 
dD({p,r,s}, 0) = {p,q,s} 
dD({p,r,s}, 1) = {p,s} 
 
dD({p,s}, 0) = {p,q,s} 
dD({p,s}, 1) = {p,s} 
 
 
EXERCÍCIO - RESOLUÇÃO 
0 1 
→ p {p, q} {p} 
q {r} {r} 
r {s} ∅ 
*s {s} {s} 
{p,q} {p,q,r} {p,r} 
{p,q,r} {p,q,r,s} {p,r} 
{p,r} {p,q,s} {p,r} 
{p,q,r,s} {p,q,r,s} {p,r,s} 
{p,q,s} {p,q,r,s} {p,r,s} 
{p,r,s} {p,q,s} {p,s} 
{p,s} {p,q,s} {p,s} 
q p s 
Início 0 
0,1 
r 
0,1 0 
1,0