AULA 5: AFN
============

DEF: Um automato finito nao deterministico (AFN) e' uma quintupla
(Q, Sigma, delta, q0, F), onde Q, Sigma, q0, F sao os mesmos elementos
de um AFD, mas a funcao de transicao delta e' definida sobre
(QxSigma)->2^Q, ou seja, dado um estado e um simbolo do alfabeto, a
transicao pode ser feita para 0, 1 ou mais estados.

Exemplo 1) (a+b)* bb

- criterio de reconhecimento para um AFN:  uma palavra e' reconhecida se
EXISTE UMA computacao que a consome e termina em estado final.

Formalmente:
DEF: a funcao de transicao estendida (delta^) 
de um AFN M=(Q,Sigma,delta, q0,F) e' uma funcao de (2^Q x Sigma*) para 2^Q
def. recursivamente como: 
   a) delta^( vazio, w) = vazio para todo w em Sigma*
   b) delta^(S, epsilon) = S para todo S subconjunto de Q
   c) delta^(S, ya) = delta'( delta^(S,y), a) para 
      a pertencente a Sigma e y pertencente a Sigma*

onde para um subconjunto S de Q: delta'(S, a) = { delta(q,a) | q em S}

DEF: a linguagem reconhecida por um AFN M=(Q,Sigma, delta, q0,F) e' o
conjunto L(M) = {w em Sigma* | delta^({q0},w) intersecao F diferente de
vazio}.   Uma palavra w e' reconhecida por M se e somente se 
delta^(q0,w) intersecao F diferente de vazio.

Exemplos:


2) (a+b)* bb (a+b)*


3) {w pertence a {a,b}* | |w| >= 3 e o terceiro simbolo da
                          direita para a esquerda e' a}

4) {w pertence a {a,b,c,d}* | o ultimo caracter de w tenha aparecido antes}

EQUIVALENCIA DE AFD'S E AFN'S
=============================

E' facil ver que AFNs sao um caso especial de AFDs.  Assim, basta
mostrar que para qualquer AFN podemos construir um AFD equivalente
para provar a equivalencia.

AFN -> AFD: 
  Seja N=(Q,Sigma, delta, q0, F). Utilize a definicao estendida delta^ e
chame de K o conjunto 2^Q.   
Defina o AFD D=(K, Sigma, delta', {q0}, {S subset Q | S intersecao F<>vazio}).
onde delta'(S,a) = Uniao(p em S)(delta(p,a))

EXEMPLO: (chame de [q0,q1] o estado correspondente ao conjunto {q0,q1}.











AFN'S COM TRASICAO EPSILON
==========================
DEF: um AFN com transicoes epsilon e' uma quintupla M=(Q, Sigma, delta,
q0,F), onde Q, delta, q0 e F sao os mesmos elementos que para o AFN.  A
funcao de transicao delta e' uma funcao de (Q x (Sigma uniao {epsilon})
para 2^Q.

Exemplo1: ( (a* bb) + (aa b*))




Exemplo2: 0* 1* 2*





Para definir a linguagem reconhecida por um AFN-epsilon precisamos fazer
algumas definicoes:

DEF: o fechamento-epsilon de um estado qi (fechamento-epsilon(qi)) e'
definido recursivamente por:
  1) qi pertence a fechamento-epsilon(qi)
  2) Seja qj um elemento de fechamento-epsilon(qi).  Se qk pertence a
delta(qj, epsilon) entao qk pertence a fechamento-epsilon(qi)

Usando o exemplo anterior:
  fechamento-epsilon(q0) = {q0, q1, q2}

Para um conjunto de estados P, 
    fechamento-epsilon(P) = Uniao(p em P) fechamento-epsilon(p)

Podemos agora estender a definicao de delta^ para AFNs com transicoes
epsilon:

DEF: a funcao de transicao estendida (delta^) 
de um AFN-epsilon M=(Q,Sigma,delta, q0,F) e' uma funcao de (Q x Sigma*) 
para 2^Q def. recursivamente como: 
   1) delta^( q, epsilon) = fechamento-epsilon(q)
   2) delta^( q, wa) = fechamento-epsilon( delta( delta^(q,w)), a ),
onde para um conjunto de estados P, delta(P,a) = Uniao(p em P) delta(p,a)

Para um conjunto de estados R:
      delta^(P,w) = Uniao(p em P) delta^(p,w)

Usando o exemplo anterior:
  delta^(q0,0) = fechamento-epsilon(delta (delta^(q0, epsilon), 0)
               = fechamento-epsilon(delta( {q0,q1,q2}, 0)
               = fechamento-epsilon( delta(q0,0) U delta(q1,0) U delta(q2,0))
  
 ...

  delta(q0,01) = fechamento-epsilon(delta( delta^(q0,0,), 1))
               = fechamento-epsilon(delta( {q0,q1,q2}, 1 )
               = fechamento-epsilon( {q1} ) = {q1, q2}


Agora estamos prontos para definir a linguagem aceita por um AFN-epsilon 
M=(Q, Sigma, delta, q0, F):
  L(M) = {w | delta^(q0, w) contem um estado em F}

AFN-epsilon ==> AFN
-------------------
Teorema: se uma linguagem L e' aceita por um AFN com transicoes epsilon
entao L e' aceita por um AFN sem transicoes epsilon.

Construcao:  seja M = (Q, Sigma, delta, q0, F) um AFN-epsilon. Construir
um AFN equiv.     M'= (Q, Sigma, delta', q0, F'), onde
F'= F uniao {q0} se fechamento-epsilon(q0) contem um estado em F
    F caso contrario

delta'(q,a) = delta^(q,a)

Usando o exemplo anterior:

           0          1      2
  ------------------------------
   q0  {q0,q1,q2}  {q1,q2}  {q2}
   q1    vazio     {q1,q2}  {q2}
   q2    vazio      vazio   {q2}


Grafico de equivalencias:

               AFD ======== AFN-epsilon
                \           /
                 \         / 
                  \       /
                     AFN