Capítulo 2 Parte II AFN's

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

*
*
2. Máquinas de Estados Finitos
Parte II
*
*
AFD - Para cada par (estado, símbolo) há transição para um único estado.
Se essa restrição for eliminada, ou seja, se para algum par (estado, símbolo), houver transições para dois ou mais estados, tem-se o que denomina
Autômato Finito Não Determinístico (AFN)
Com isso, em um AFN podem existir várias computações possíveis para a mesma palavra.
2.3. Autômatos Finitos Não Determinísticos
*
*
2.3. Autômatos Finitos Não Determinísticos
Em todo ponto de indecisão, a máquina adivinha qual escolha (se houver alguma) leva a uma computação que resulta em sucesso no reconhecimento.
*
*
Formalmente: Um AFN é uma quíntupla (E, ∑, δ, I, F), onde:
E: conjunto finito de estados
∑: alfabeto
δ: E x ∑ → P(E): função de transição
I é um subconjunto de E: conjunto não vazio de estados iniciais.
F é um subconjunto de E: conjunto de estados finais.
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
Como estabelece a função para AFN, os AFD são casos particulares de AFN, onde o conjunto de estados mapeados por um par (e, a) via δ é unitário.
*
*
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
Alem do fato de que, em geral, um AFN não pode ser implementado tão diretamente quanto um AFD, para todo AFN existe um AFD equivalente.
Então, pergunta-se: por que o conceito de AFN tem alguma importância?
	Em primeiro lugar, algumas vezes é mais fácil construir um AFN do que um AFD. 
	Em segundo lugar, além de ser mais fácil, o AFN pode ser mais claro do que um AFD equivalente, dando mais confiança quanto a sua correção. Assim, justifica-se, pelo menos em alguns casos, construir o AFN e usar um algoritmo para obter um AFD equivalente. 
	Em terceiro lugar, o conceito de não determinismo é importante em outras áreas da Ciência da Computação.
*
*
2.3.1. Equivalência entre AFDs e AFNs
2.3. Autômatos Finitos Não Determinísticos (AFNs)
*
*
2.3.1. Equivalência entre AFDs e AFNs
2.3. Autômatos Finitos Não Determinísticos (AFNs)
*
*
2.3.1. Equivalência entre AFDs e AFNs
2.3. Autômatos Finitos Não Determinísticos (AFNs)
*
*
2.3.1. Equivalência entre AFDs e AFNs
2.3. Autômatos Finitos Não Determinísticos (AFNs)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
Observação: Dados dois AFNs M1 e M2, pode-se construir um AFNλ que reconhece L(M1)L(M2) simplesmente colocando-se uma transição sob λ de cada estado final de M1 para cada estado inicial de M2
Os estados iniciais do AFNλ corresponderiam aos estados iniciais de M1 e os estados finais seriam os estados finais de M2.
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
Tem algum par (e, a) tal qual se eu realizar a transição eu vou cair em algum estado que aceite transição vazia?
Se eu posso chegar a um estado e sob o processamento do símbolo a, e do estado e existe uma transição  para um estado e’, significa que eu posso ir do estado e para o estado e’ sob o processamento do símbolo a.
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
2.3.2. AFN Estendido (AFNE)
2.3. Autômatos Finitos Não Determinísticos (AFN’s)
*
*
*
*
*
*
*
*
*
*