Linguagens Formais e Autômatos - Leandro Dionízio - Aula 04 EquivalênciaAFD_AFND

Prévia do material em texto

Linguagens Formais
Leandro Dionízio Ramos
1
Equivalência entre AFD e AFND
• A partir de um AFD é possível criar um AFND 
equivalente?
– Basta criar um AFND cuja função leva a dois 
estados diferentes com o mesmo símbolo de 
entrada.
2
Equivalência entre AFD e AFND
• Um AFND pode se transformar em um AFD 
equivalente.
• Dois autômatos são considerados equivalentes 
se aceitam a mesma linguagem.
3
Equivalência entre AFD e AFND
• Algoritmo de conversão de AFND para AFD
1) Tome o diagrama de transição do AFND e crie para 
cada conjunto de estados, um novo estado onde o 
rótulo é o próprio conjunto.
2) Complete as transições de cada novo estado 
acompanhando o comportamento de cada estado 
individualmente e tomando a união dos estados 
acessados.
3) Adicione como estados finais aqueles estados que tem 
como rótulo um estado final.
4
Equivalência entre AFD e AFND
• Algoritmo de conversão de AFND para AFD
4) Elimine os estados nunca acessados a partir do estado 
inicial.
5) Complete o AFD da seguinte forma:
a) Q do AFD são os estados resultantes dos passos até este 
ponto.
b) O alfabeto não é alterado
c) A construção do delta já foi mencionada.
d) O estado inicial não se altera
e) Os estados finais são a união de todos os estados finais do 
delta resultante.
5
Equivalência entre AFD e AFND
• Conversão de AFND para AFD
seja M = ({q0, q1, q2}, {0, 1}, δ, q0, {q2})
6
δ 0 1
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
Equivalência entre AFD e AFND
• Transições do estado vazio + estados 
resultantes da junção de dois ou mais estados 
da transição.
• A transição {q0 q1} é um conjunto de estados.
7
δ 0 1
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
Equivalência entre AFD e AFND
• As transição {q0 q1} serão a união das 
transições de cada estado do conjunto.
8
δ 0 1
Ø Ø Ø
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
{q0 q1}
Equivalência entre AFD e AFND
• Neste caso a transição {q0 q1} passa a ser um novo 
estado na tabela.
– Obs.: Algumas literaturas sugerem a adição do estado Ø.
• Quando {q0 q1} recebe 0, a transição é {q0 q1} U Ø.
9
δ 0 1
Ø Ø Ø
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
{q0 q1} {q0 q1} {q0 q2}
Equivalência entre AFD e AFND
• Quando {q0 q1} recebe 0, a transição é {q0 q1} + Ø.
• Quando {q0 q1} recebe 1, a transição é q0 + q2 = {q0 q2} 
(novo conjunto de estados).
10
δ 0 1
Ø Ø Ø
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
{q0 q1} {q0 q1} {q0 q2}
Equivalência entre AFD e AFND
• Como {q0 q2} ainda não existe na tabela de transição é 
preciso adiciona-lo como um novo estado.
11
δ 0 1
Ø Ø Ø
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
{q0 q1} {q0 q1} {q0 q2}
{q0 q2} {q0 q1} {q0}
Equivalência entre AFD e AFND
• M = ({q0, q1, q2}, {0, 1}, δ, q0, {q2})
{q2} = estado de aceitação, então todos os estados que 
tiverem q2 também serão estados de aceitação.
12
δ 0 1
Ø Ø Ø
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
{q0 q1} {q0 q1} {q0 q2}
{q0 q2} {q0 q1} {q0}
Equivalência entre AFD e AFND
• Será que podemos simplificar a tabela de transição 
identificada?
• Será que temos estados inacessíveis que podem ser 
removidos?
13
δ 0 1
Ø Ø Ø
q0 {q0 q1} {q0}
q1 Ø {q2}
q2 Ø Ø
{q0 q1} {q0 q1} {q0 q2}
{q0 q2} {q0 q1} {q0}
Equivalência entre AFD e AFND
• Para facilitar a identificação dos estados inacessíveis, 
podemos renomear os estados por letras.
– Ø = A
– q0 = B
– q1 = C
– q2 = D
– {q0 q1} = E
– {q0 q2} = F
14
δ 0 1
A A A
B E B
C A D
D A A
E E F
F E B
Equivalência entre AFD e AFND
• Os estados inacessíveis são os estados que não existe 
transição para eles.
• Quem acessa o estado C? Retirando o estado C, quem 
acessará o estado D?...
– Ø = A
– q0 = B
– q1 = C
– q2 = D
– {q0 q1} = E
– {q0 q2} = F
15
δ 0 1
A A A
B E B
C A D
D A A
E E F
F E B
Equivalência entre AFD e AFND
• Tabela simplificada: 
16
δ 0 1
B E B
E E F
F E B
δ 0 1
q0 {q0 q1} {q0}
{q0 q1} {q0 q1} {q0 q2}
{q0 q2} {q0 q1} {q0}
Equivalência entre AFD e AFND
• Tabela simplificada: 
17
AFD: M = ({q0, {q0 q1}, {q0 q2}}, {0, 1}, δ, q0, {q0 q2})
AFND: M = ({q0, q1, q2}, {0, 1}, δ, q0, {q2})
δ 0 1
q0 {q0 q1} {q0}
{q0 q1} {q0 q1} {q0 q2}
{q0 q2} {q0 q1} {q0}
Equivalência entre AFD e AFND
• Portanto, os AFNDs não são mais expressivos do que 
os AFDs
– São formalismos equivalentes
– Ambos reconhecem a mesma classe de linguagens
18
Exercício - AFND
Transformar de AFND para AFD:
19
A) B)
C)