Equivalência entre AFnD e AFD

Discussão sobre autômatos finitos determinísticos, não determinísticos e a equivalência entre os formalismos

1. PROF. WELLINGTON DELLA MURA
CIÊNCIA DA COMPUTAÇÃO (CAMPUS LUIZ MENEGHEL -BANDEIRANTES)
UNIVERSIDADE ESTADUAL DO NORTE DO PARANÁ
Equivalência entre Autômatos Finitos
Determinísticos e Não Determinísticos
Teoria da Computação

2. ROTEIRO
1.Determinismo
2.Não determinismo
3.Computação dos autômatos finitos
4.Equivalência entre AFND e AFD
5.Simulações com JFLAP
6.Resumo da Aula

3. ANTES DE INICIAR
RESUMO DO QUE JÁ FOI ESTUDADO
Máquina de
Estados Finitos
Palavra w
ACEITA
REJEITA
baaba
Função de
Transiçãoq
0
????????????
0,??????=??????
1
•Umalinguagemformalconsisteemumconjuntodepalavras
quepossuemasmesmaspropriedades(oupadrões).
•Cadapalavraéumasequenciadesímbolosdeumalfabeto.
Máquina de Estados Finitos
Formalismo Reconhecedor: Autômato Finito
Importante:

4. AUTÔMATOS
FINITOS
DETERMINÍSTICOS
Formalismo Reconhecedor
Recebe uma palavra we indica se ela é aceitaou rejeitada
Segue critérios e propriedades da Linguagem Formal L
Para cada símbolo lido, alterna sua
computação para um novo estado
a b
→q
0q
1 q
2
Q
1q
n
-
.........
*q
nq
1 q
2

5. AUTÔMATOS
FINITOS NÃO
DETERMINÍSTICOS
Da mesma forma que o AFD, recebe uma palavra we indica se
ela é aceitaou rejeitada
A principal diferença:
Para cada símbolo lido, pode alternar sua
computação para
mais deum novo estado
a b
→q
0{q
1, ..., q
n}{q
1, ..., q
n}
Q
1{q
2, q
3}
{}
...... ...
*q
n{q
2} {q
2}

6. EXEMPLO
COMPUTAÇÃO DOS AUTÔMATOS FINITOS
Considere a linguagem
L = {w ∈{a, b, c}* | w termina com cab}
O autômato finito determinístico capaz de reconhecer L pode ter
qualquer prefixo presente em{a, b, c}*mas deve buscar o padrão cab
no final da palavra.
Por exemplo: ababacab, bbbbcab, cabcab

7. SOLUÇÃO
DETERMINÍSTICA

8. COMPUTAÇÃO DA SOLUÇÃO DETERMINÍSTICA
acacab
Considere a entrada

9. SOLUÇÃO
NÃO DETERMINÍSTICA

10. COMPUTAÇÃO DA SOLUÇÃO DETERMINÍSTICA
acacab
Considere a entrada

11. ALGORITMO
EQUIVALÊNCIA ENTRE AFNDE AFD
Prova: (por indução)
Mostra que
a partir de um AFND Mqualquer
É possível construir um AFD MDque realize as mesmas computações
MDsimula M
Logo, AFND → AFD
estados de MDsimulam combinações de estados alternativos de M

12. EQUIVALÊNCIA ENTRE AFNDE AFD
COMO FUNCIONA O ALGORITMO

13. EQUIVALÊNCIA ENTRE AFNDE AFD
DEFINIÇÃO FORMAL DO ALGORITMO
M = (, Q, , q0, F) um AFN qualquer.
AFD construído MD = (, QD, D, q0, FD)
•QD –todas as combinações, sem repetições, de estados de Q
•notação q1q2qn
•ordem não distingue combinações: quqv= qvqu
•imagem de todos os estados alternativos de M
•D: QD →QD
D(q1qn, a) = p1pmsse*({ q1, , qn}, a) = { p1, , pm} em particular:
D(q1qn, a) é indefinida sse*({ q1, , qn}, a) = 
•q0–estado inicial
•FD -conjunto de estados q1q2qnpertencentes a QD
alguma componente qipertence a F, para i em { 1, 2, , n }

14. EXEMPLO DE APLICAÇÃO
SOLUÇÃO NÃO DETERMINÍSTICA
Q = {q
0, q
1, q
2, q
3}
∑ = {a, b, c}
F = {q
3}
 a b c
→q
0{q
0}{q
0}{q
0, q
1}
q
1{q
2} {} {}
q
2{} {q
3} {}
*q
3{} {} {}

15. EXEMPLO DE APLICAÇÃO
CONSTRUÇÃO DOS ESTADOS
∑ = {a, b, c} se mantém
Q = {q
0, q
1, q
2, q
3}
Q
d= 2
Q
↳2
Q
={{q
0},{q
1},{q
2},{q
2},{q
0, q
1}... }
q
0d= <q0>
F = {q
3}
F
d= {<q1q3>, <q0q3>, <q1q2q3>,...}
↳Todoestado de F
dque contém um elemento de F
q0q1q2q3 estado
0001 <q3>
0010 <q2>
0011 <q2q3>
0100 <q1>
0101 <q1q3>
0110 <q1q2>
0111 <q1q2q3>
...
1111<q1q2q3q4>

16. EXEMPLO DE APLICAÇÃO
CONSTRUÇÃO DAS TRANSIÇÕES
Q
d= {{q
0},{q
1},{q
2},{q
2},{q
0, q
1}... }
Para 
d (<q0>, c) => (q0, c)
(q0, c) = {q0, q1}
↳
d(<q0>, c) = <q0q1>
Para 
d (<q0q1>, a) => (q0, a) (q1, a)
(q0, a) = {q0}
(q1, a) = {q2}
↳
d(<q0q1>, a) = <q0q2>
 a b c
<q0><q0> <q0> <q0q1>
<q1><q2> - -
<q2> - <q3> -
<q3> - - -
<q0q1><q0q2><q0> <q0q1>
...
<q0q1q2q3><q0q2><q0q3><q0q1>

17. EXEMPLO DE APLICAÇÃO
CONSTRUÇÃO DAS TRANSIÇÕES
Q
d= {{q
0},{q
1},{q
2},{q
2},{q
0, q
1}... }
Para 
d (<q0>, c) => (q0, c)
(q0, c) = {q0, q1}
↳
d(<q0>, c) = <q0q1>
Para 
d (<q0q1>, a) => (q0, a) (q1, a)
(q0, a) = {q0}
(q1, a) = {q2}
↳
d(<q0q1>, a) = <q0q2>
 a b c
<q0>
<q0> <q0> <q0q1>
<q1>
<q2> - -
<q2>
- <q3> -
<q3>
- - -
<q0q1>
<q0q2><q0><q0q1>
...
<q0q1q2q3>
<q0q2><q0q3><q0q1>

18. EXEMPLO DE APLICAÇÃO
PODA DAS TRANSIÇÕES (OTIMIZAÇÃO)
 a b c
<q0>
<q0> <q0> <q0q1>
<q0q1>
<q0q2> <q0> <q0q1>
<q0q2>
<q0> <q0q3> <q0q1>
<q0q3>
<q0> <q0> <q0q1>

19. RESULTADO