Aula_06___Aut_matos_Finitos_N_o_Determin_sticos__Parte_2_

Prévia do material em texto

LINGUAGENS FORMA IS E AUTÔMATOS
Prof. Mário Sérgio Cavalcante
DCA0212
Natal - Rio Grande do Norte
Departamento de Engenharia de Computação e Automação
Universidade Federal do Rio Grande do Norte
marioffcavalcante@dca.ufrn.br
Aula 6 - Autômatos Finitos Não-Determinísticos (Parte 2)
SUMÁRIO DA AULA
Teorema 1,39
Equivalência entre AFN e AFDs - Caso Simples
Exemplo (Caso Simples)
Equivalência entre AFN e AFDs - Caso Geral
Exemplo (Caso Geral)
Exercícios
02
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 2 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFdS
Na aula de hoje mostraremos que AFDs e AFNS reconhecem a
mesma classe de linguagens, como veremos no teorema abaixo ;
Definição :
Dizemos que duas máquinas são equivalentes se elas reconhecem a mesma
linguagem
Teorema : 1.39
Todo autômato finito não-determinístico tem um autômato finito determinístico
equivalente.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 3 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Qual o processamento da cadeia - w = 11111?
q1
1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Qual o processamento da cadeia - w = 11111?
q1
1
q1 q2 q3
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Qual o processamento da cadeia - w = 11111?
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Qual o processamento da cadeia - w = 11111?
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4 q4
1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Qual o processamento da cadeia - w = 11111?
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4 q4
1
q1 q2 q3 X q4 q4 q4
1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Computação do AFN
Qual o processamento da cadeia - w = 11111?
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4 q4
1
q1 q2 q3 X q4 q4 q4
1
q1 q2 q3 X q4 q4 q4 q4
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 4 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Como a computação da cadeia termi-
nou em um estado de aceitação (q4) ,
logo :
Cadeia aceita.
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4 q4
1
q1 q2 q3 X q4 q4 q4
1
q1 q2 q3 X q4 q4 q4 q4
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 5 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Propriedades derivadas da definição de função de transição
Computação do AFN
1. Se um mesmo estado aparece várias
vezes no mesmo passo da computa-
ção, então os ramos correspondentes
(descendentes na árvores) são idênti-
cos ;
⇒ Redundância pode ser eliminada.
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4 q4
1
q1 q2 q3 X q4 q4 q4
1
q1 q2 q3 X q4 q4 q4
q4
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 6 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Propriedades derivadas da definição de função de transição
1. Se um mesmo estado aparece várias
vezes no mesmo passo da computa-
ção, então os ramos correspondentes
(descendentes na árvores) são idênti-
cos ;
⇒ Logo, podemos considerar que, a cada
passo da computação, o AFN pode estar
em um subconjunto de possíveis estados :
No passo 0 (inicio), em que {q1} ;
Após o 1º passo, em {q1, q2, q3} ;
Após o 2º passo, em {q1, q2, q3, q4} ;
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4
1
q1 q2 q3 X q4
1
q1 q2 q3 X q4
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 7 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Propriedades derivadas da definição de função de transição
q1
1
q1 q2 q3
1
Xq1 q2 q3 q4
1
q1 q2 q3 X q4
1
q1 q2 q3 X q4
1
q1 q2 q3 X q4
2. O conjunto de estados seguintes só depende do
conjunto de estados atual e o próximo símbolo a
ser lido, independentemente do passo da
computação
Observe que, dado o conjunto
{q1,q2,q3,q4} e o símbolo "1", o conjunto
resultante é sempre {q1,q2,q3,q4}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 8 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Propriedades derivadas da definição de função de transição
q1 q3
q2 X
q1 q3X
q2 q3
q2 q3 q1 q3
Observe que, dado o conjunto
{q2,q3} e o símbolo lido "a", o
conjunto resultante é sempre
{q1,q2,q3}
q3q2
a
b
a
a,b
ε
q1
Outro exemplo da propriedade 2: 
a
b
a
a
b
a
q1 q3 q2 q3
Xq2Xq3
Computação do AFN original
Cadeia aceita, pois q1 é de aceitação
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 9 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
q1 q3
q2 X
q1 q3X
q2 q3
q2 q3 q1 q3
Observe que, dado o conjunto
{q2,q3} e o símbolo lido "a", o
conjunto resultante é sempre
{q1,q2,q3}
q3q2
a
b
a
a,b
ε
q1
Outro exemplo da propriedade 2: 
a
b
a
a
b
a
q1 q3 q2 q3
Xq2Xq3
{q1,q3}
{q1,q3}
a
{q2}
b
{q2,q3}
a
a
{q1,q2,q3}
{q2,q3}
b
{q1,q2,q3}
a
Computação do AFD 
 equivalenteComputação do AFN original
Cadeia aceita, pois q1 é de aceitação
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 10 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Exemplo - Teorema 1.39 (Caso Simples)
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 10 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
32
ab
a
a,b
1
Prova do Teorema 1.39: Conversão de um AFN em um AFD equivalente
Denotamos por o AFN e seus componentes por N = (Q, Σ,δ, q0, F);
Precisamos realizar a construção completa do AFD M = (Q', Σ,δ', q'0,
F');
Primeiroo caso mais simples: sem transições com ε;
Ilustraremos cada passo com o exemplo ao lado
1. Q' = P(Q)
Cada estado de M representa um subconjunto de estados de N;
Em nosso exemplo:
Q' = {∅, {1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}};
Nem todos esses estados são necessários.
2. q'0 = {q0}: O estado inicial de M corresponde ao subconjunto contendo
somente o estado inicial de N
Em nosso exemplo: q0' = {1}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 11 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
32
ab
a
a,b
1
Prova do Teorema 1.39: AFN → AFD (sem transições com )
3. F' = { possui um estado de aceitação de N}
O AFD equivalente aceita uma cadeia se, após a leitura
do último símbolo, ele parar em um estado que "possua"
um dos estados de aceitação do AFN original;
Em nosso exemplo:
F' = {{1},{1,2},{1,3},{1,2,3}};
4. ' = para todo e ,
 
Em cada passo da computação do AFN original, este
pode estar em vários estados possíveis 
 simultaneamente;
Dado um símbolo α a ser lido, o subconjunto de estados
subsequentes será determinado inspecionando-se as
imagens de (cada qual um
subconjunto de ) e unindo essas imagens.
q1
q2
q2 q3
q2 q3 q1
q3 X q2
q1 q2 q3
b
a
a
b
a
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 12 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Conversão para AFD :
δ′({1}, a) = δ{(1, a)} = ∅
δ′({1}, b) = δ{(1, b)} = {2}
Se um ramo da computação do AFN
vai para o estado vazio, esse ramo
para imediatamente a execução e re-
jeita a cadeia.
No AFD correspondente, esse estado
é um estado absorvente, ou seja, uma
vez nele, o AFD não sai mais até o final
da leitura da cadeia, e então, rejeita.
Assim :
δ′(∅, a) = ∅
δ′(∅, b) = ∅
δ′ a b
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 13 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Conversão para AFD :
δ′({1}, a) = δ{(1, a)} = ∅
δ′({1}, b) = δ{(1, b)} = {2}
Se um ramo da computação do AFN
vai para o estado vazio, esse ramo
para imediatamente a execução e re-
jeita a cadeia.
No AFD correspondente, esse estado
é um estado absorvente, ou seja, uma
vez nele, o AFD não sai mais até o final
da leitura da cadeia, e então, rejeita.
Assim :
δ′(∅, a) = ∅
δ′(∅, b) = ∅
δ′ a b
→{1} ∅ {2}
→ {∅} ∅ ∅
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 14 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Conversão para AFD :
δ′({2}, a) = δ{(2, a)} = {2, 3}
δ′({2}, b) = δ{(2, b)} = {3}
δ′({2, 3}, a) = δ{(2, a)} ∪ δ{(3, a)} =
{2, 3} ∪ {1} = {1, 2, 3}
δ′({2, 3}, b) = δ{(2, b)} ∪ δ{(3, b)} =
{3} ∪ ∅ = {3}
δ′({3}, a) = {1}
δ′({3}, b) = ∅
δ′ a b
{1} ∅ {2}
{∅} ∅ ∅
→ {2} {2,3} {3}
→ {2,3} {1,2,3} {3}
→ {3} {1} ∅
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 15 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Conversão para AFD :
δ′({1, 2, 3}, a) = δ(1, a) ∪ δ(2, a) ∪ δ(3, a)
= ∅ ∪ {2, 3} ∪ {1}
= {1, 2, 3}
δ′({1, 2, 3}, b) = δ(1, b) ∪ δ(2, b) ∪ δ(3, b)
= {2} ∪ {3} ∪ {∅}
= {2, 3}
δ′ a b
{1} ∅ {2}
{∅} ∅ ∅
{2} {2,3} {3}
{2,3} {1,2,3} {3}
{3} {1} ∅
→{1,2,3} {1,2,3} {2,3}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 16 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
δ′ a b
{1} ∅ {2}
{∅} ∅ ∅
{2} {2,3} {3}
{2,3} {1,2,3} {3}
{3} {1} ∅
{1,2,3} {1,2,3} {2,3}
M1 : ( {∅, {1}, {2}, {3}, {2, 3}, {1, 2, 3}},
{a, b}, δ′, {1}, {{1}, {1, 2, 3}})
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 17 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência - Caso Geral
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 17 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Prova do Teorema 1.39 : Conversão de um AFN em um AFD equi-
valente
Denotamos por o AFN e seus componentes por N = (Q,Σ, δ, q0,F ) ;
Precisamos realizar a construção completa do AFD M = (Q′,Σ, δ′, q′0,F
′);
Caso mais geral : AFNs que possuem transições com � (ou λ)
Q’ e F’ : não mudam em relação à demostração do caso mais simples ;
q′0 e δ’ : Precisam ser adaptados ;
Primeiro, precisamos verificar, para cada estado q ∈ Q, qual é o
conjunto de estados alcançáveis a partir de q por transições com
cadeias vazias (� ou λ)
e(q) = {p ∈ Q|p pode ser alcançado a partir de q viajando-se por 0 ou mais
transições com �}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 18 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
e(q) = {p ∈ Q|p pode ser alcançado a partir de q viajando-se por 0 ou mais
transições com �}
Considere o exemplo abaixo :
a
b
a
a
e(q0) = {q0,q1,q2,q3}
q0 é alcançável a partir dele mesmo viajando-se com 0 transições � ;
q1 e q3 é alcançável a a partir q0 viajando-se com 1 transições � ;
q2 é alcançável a partir q0 viajando-se com 2 transições � ;
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 19 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
e(q) = {p ∈ Q|p pode ser alcançado a partir de q viajando-se por 0 ou mais
transições com �}
Considere o exemplo abaixo :
a
b
a
a
e(q0) = {q0,q1,q2,q3}
q0 é alcançável a partir dele mesmo viajando-se com 0 transições � ;
q1 e q3 é alcançável a a partir q0 viajando-se com 1 transições � ;
q2 é alcançável a partir q0 viajando-se com 2 transições � ;
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 19 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
e(q) = {p ∈ Q|p pode ser alcançado a partir de q viajando-se por 0 ou mais
transições com �}
Considere o exemplo abaixo :
a
b
a
a
e(q0) = {q0, q1, q2, q3}
e(q1) = {q1, q2}
e(q2) = {q2}
e(q3) = {q3}
e(q4) = {q2, q4}
e(q5) = {q5}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 20 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
e(q) = {p ∈ Q | p pode ser alcançado a partir de q viajando-se
por 0 ou mais transições �} ;
Por que e(q) é necessário?
Porque, se q possui transições com �, uma que o AFN entra no estado q, ele
pode permanecer permanecer em q ou ir para qualquer um dos estados de
e(q) ;
Isso precisa ser considerado pelo AFD equivalente que simulará o AFN origi-
nal.
Então, temos a seguinte função : dado R ⊆ Q :
E(R) = {p ∈ Q} pode ser alcançado a partir de R viajando-se por 0 ou mais
transições �} ;
E(R) =
⋃
q∈R
e(q) (1)
E(R) é umamera extensão de e(q) : ao invés de olhar para um único estado,
olha para um subconjunto de estados de N.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 21 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD
E(R) =
⋃
q∈R
e(q)
Voltando ao nosso exemplo :
a
b
a
a
E({q0,q4}) =?
E({q1,q5}) =?
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 22 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD
E(R) =
⋃
q∈R
e(q)
Voltando ao nosso exemplo :
a
b
a
a
E({q0,q4}) = e(q0) ∪ e(q4)
E({q1,q5}) = e(q1) ∪ e(q5)
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 23 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD
E(R) =
⋃
q∈R
e(q)
Voltando ao nosso exemplo :
a
b
a
a
E({q0,q4}) ={q0,q1,q2,q3} ∪ {q2,q4} = {q0,q1,q2,q3,q4}
E({q1,q5}) =?
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 24 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD
E(R) =
⋃
q∈R
e(q)
Voltando ao nosso exemplo :
a
b
a
a
E({q0,q4}) ={q0,q1,q2,q3} ∪ {q2,q4} = {q0,q1,q2,q3,q4}
E({q1,q5}) = {q1,q2} ∪ {q5} = {q1,q2,q5}
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 25 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
Com E(R), podemos agora apresentar q′0 e δ
′
1. q′0 = e(q0) → O AFD equivalente deve começar no subconjunto
de estados em que o AFN iniciaria antes de ler qualquer símbolo
No nosso exemplo inicial da aula :
Toda computação do AFN original pode começar sobre um dos estados q1 ou
q3
Isso é refletido pelo estado inicial do AFD equivalente q′0 = e(q1) = {q1, q3}
q3q2
a
b
a
a,b
ε
q1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 26 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
2. δ′ : para todo R ∈ Q′ e a ∈ Σ.
δ′(R,a) = {q ∈ Q|q ∈ E(δ(r ,a))para algum r ∈ R}
δ′(R,a) =
⋃
r∈R E(δ(r ,a))
Devemos olhar não apenas para cada imagem δ(r , a), mas também para
respectivos estados alcançáveis por transições �.
q3q2
a
b
a
a,b
ε
q1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
2. δ′ : para todo R ∈ Q′ e a ∈ Σ.
δ′(R,a) = {q ∈ Q|q ∈ E(δ(r ,a))para algum r ∈ R}
δ′(R,a) =
⋃
r∈R E(δ(r ,a))
Devemos olhar não apenas para cada imagem δ(r , a), mas também para
respectivos estados alcançáveis por transições �.
q3q2
a
b
a
a,b
ε
q1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
2. δ′ : para todo R ∈ Q′ e a ∈ Σ.
δ′(R,a) = {q ∈ Q|q ∈ E(δ(r ,a))para algum r ∈ R}
δ′(R,a) =
⋃
r∈R E(δ(r ,a))
Devemos olhar não apenas para cada imagem δ(r , a), mas também para
respectivos estados alcançáveis por transições �.
q3q2
a
b
a
a,b
ε
q1
 
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
2. δ′ : para todo R ∈ Q′ e a ∈ Σ.
δ′(R,a) = {q ∈ Q|q ∈ E(δ(r ,a))para algum r ∈ R}
δ′(R,a) =
⋃
r∈R E(δ(r ,a))
Devemos olhar não apenas para cada imagem δ(r , a), mas também para
respectivos estados alcançáveis por transições �.
q3q2
a
b
a
a,b
ε
q1
 { }
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
2. δ′ : para todo R ∈ Q′ e a ∈ Σ.
δ′(R,a) = {q ∈ Q|q ∈ E(δ(r ,a))para algum r ∈ R}
δ′(R,a) =
⋃
r∈R E(δ(r ,a))
Devemos olhar não apenas para cada imagem δ(r , a), mas também para
respectivos estados alcançáveis por transições �.
q3q2
a
b
a
a,b
ε
q1
 { }
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
AFN→ AFD (caso geral)
2. δ′ : para todo R ∈ Q′ e a ∈ Σ.
δ′(R,a) = {q ∈ Q|q ∈ E(δ(r ,a))para algum r ∈ R}
δ′(R,a) =
⋃
r∈R E(δ(r ,a))
Devemos olhar não apenas para cada imagem δ(r , a), mas também para
respectivos estados alcançáveis por transições �.
q3q2
a
b
a
a,b
ε
q1
 { }
 = 
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Exemplo - Teorema 1.39 (Caso Geral)
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 27 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 28 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
Conversão	para	AFD:	
Estado	inicial:	 ;
Função	de	transição	 	:	(começamos	pelo	estado	inicial)
								 	
								
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 29 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
Conversão	para	AFD:	
Estado	inicial:	 ;
Função	de	transição	 	:	(começamos	pelo	estado	inicial)
								 	
								
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 30 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
Conversão	para	AFD:	(Cont)
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 31 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
Conversão	para	AFD:	(Cont)
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 32 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso GeralExemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 33 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Exemplo :
32
a
b
a
a,b
ε
1
C
om
pu
ta
çã
o	
do
	A
FN
	o
ri
gi
na
l
C
om
pu
ta
çã
o	
do
	A
FD
eq
ui
va
le
nt
e
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 34 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Teorema 1.39
Todo autômato finito não-determinístico tem um autômato finito deter-
minístico equivalente.
Corolário 1.40
Uma linguagem é regular se e somente se, algum autômato finito não-
determinístico a reconhece.
Demostração direta :
A é regular se ⇔ um AFD reconhece A︸ ︷︷ ︸
Definição 1.16 - Linguagem Regular
⇔ um AFN reconhece A︸ ︷︷ ︸
Teorema 1.16 - Linguagem Regular
.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 35 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Exercícios
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 35 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Equivalência entre AFNs e AFDs
Converta os AFNs e abaixo para AFDs equivalentes :
b
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 36 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Conclusão
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 36 / 38
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Dúvidas??
Dúvidas, Sugestões e Comentários :
mariocavalcante@dca.ufrn.br
Mário Sérgio Cavalcante
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 37 / 38
mariocavalcante@dca.ufrn.br
Equivalência entre AFNs e AFDs Exemplo - Teorema 1.39 (Caso Simples) Equivalência - Caso Geral Exemplo - Teorema 1.39 (Caso Geral) Exercícios Conclusão
Bibliografia :
Fontes :
Spiser, M. Introdução à Teoria da Computação.2ª ed., Ed. Thomson.
Notas de aula do professor Marcelo S. Lauretto.
Mário Sérgio Cavalcante UFRN Noções de Algoritmos Natal - Rio Grande do Norte 38 / 38
	Equivalência entre AFNs e AFDs
	Exemplo - Teorema 1.39 (Caso Simples)
	Equivalência - Caso Geral
	Exemplo - Teorema 1.39 (Caso Geral)
	Exercícios
	Conclusão
	Bibliografia: 
	anm0: 
	0.4: 
	0.3: 
	0.2: 
	0.1: 
	0.0: