AULA 7: PROPRIEDADES DAS LINGUAGENS REGULARES
==============================================

1) MINIMIZACAO DE ESTADOS DE UM AFD
===================================

DEF: Seja um AFD=(Q, Sigma, delta, q0,F).  Estados q e p pertencentes a Q
sao equivalentes se para qualquer palavra w em Sigma*, delta^(q,w) pertence
a F se e somente se delta^(p,w) pertence a F.

Figura ilustrativa:









Exemplo:
    
   b x
   c x x
   d x x x
   e   x x x
   f x x x   x
   g x x x x x x
   h x   x x x x x
     a b c d e f g

Algoritmo:
 - para cada p em F e q em Q-F marque (p,q)
 - para par de estados (p,q) em (FxF) ou (Q-F)x(Q-F) faca
      - se para algum simbolo a (delta(p,a), delta(q,a)) esta marcado entao
         - marque (p,q)
         - recursivamente marque todos os pares na lista de (p,q) e nas
           listas dos pares marcados neste passo
        senao se delta(p,a) diferente de delta(q,a) entao
         - para todos os simbolos de entrada a faca
             - coloque (p,q) na lista para (delta(p,a), delta(q,a))
               a nao ser que delta(p,a) = delta(q,a)
           
    






2) PROPRIEDADES DE FECHAMENTO DAS LINGUAGENS REGULARES
------------------------------------------------------
Uma familia de linguagens e' dita fechada sob uma determinada operacao se a
aplicacao desta operacao em membros da familia produzem membros da familia.

Teorema: se L1 e L2 sao linguagens regulares, entao L1 uniao L2,
L1.L2, L1*, complemento de L1, e L1 intersecao L2 sao linguagens regulares.

Prova: construcao de um automato que aceite cada uma das linguagens.
1) L1 uniao L2, L1.L2, L1* : construcao ja' explicada na transformacao de
   expressao regular para automato
2) complemento de L1:  estados finais passam a ser nao finais, e nao finais
   passam a ser finais. Note que e' necessario que o automato original seja
   deterministico (sem transicoes epsilon)
3) L1 intersecao L2: 
   Seja M1=(Q1, Sigma, delta1, q1, F1) e M2=(Q2, Sigma, delta2, q2, F2)
dois DFAs que aceitam as linguagens L1 e L2 respectivamente.
Construir o DFA M=(Q1xQ2, Sigma, delta, [q1,q2], F1xF2), onde para todo
p1 em Q1, p2 em Q2 e a em Sigma
   delta([p1,p2],a) = [delta1(p1,a), delta2(p2,a)]

Exemplo:






3) LINGUAGENS QUE NAO SAO REGULARES:
====================================
Exemplo de uma linguagem que nao e' regular:
  {a^i b^i | i >= 0}

Um DFA simplificado que aceita esta linguagem teria o seguinte formato:









COMO PROVAR QUE UMA LINGUAGEM NAO E' REGULAR:
---------------------------------------------
--> PUMPING LEMMA (ler pags. 97-100 do livro do Prof. Newton Vieira)


Pumping Lemma 
    Exemplos: {a^i b^i | i >= 0}
              {ww | w in {a,b}*}
              {xyx^R | x, y in {a,b}*} => regular
              {w in {a,b}* | #a's = #b's} usando intersecao com a^* b^*