AULA 6: LINGUAGENS E CONJUNTOS REGULARES (CAPITULO 7)
======================================================

1) EQUIVALENCIA DE AUTOMATOS FINITOS E EXPRESSOES REGULARES
-----------------------------------------------------------
Teorema: uma linguagem L e' aceita por um DFA se e somente se e' definido
por uma expressao regular.

- expressao regular --> automato finito (com transicoes epsilon)

Seguindo a definicao recursiva de uma expressao regular:
  - \emptyset e' uma expressao regular

  - \epsilon e' uma expr. regular

  - para toda a em Sigma, 'a' e' uma expr. regular

  - se r e s sao expr. regulares, entao (r+s), (rs) e r* sao expr. regulares
  













Exemplo: construir um NFA que aceita a linguagem gerada pela expr. regular 
(a+b)*ba













- DFA --> expressao regular

  - utiliza uma extensao de automatos que aceita expressoes regulares ao
inves de simbolos do alfabeto nas transicoes entre estados.

Algoritmo:
  1) se o automato tiver transicoes incidentes no estado inicial S, criar
um novo estado inicial S', com uma transicao epsilon de S' para S
  2) se o automato tiver mais de um estado final ou transicoes incidentes
em um estado final, criar um novo estado final F, com transicoes epsilon
dos estados finais originais para F 
  3) eliminar as transicoes paralelas, ou seja, se houver transicoes do
estado qi para qj com os simbolos a1, a2,... an, substituir estas
transicoes por uma unica a1 + a2 + ... + an
  4) Seja w(i,j) a expressao de um arco do estado i para o estado j.
     repetir ate' que os unicos nodos do automato sejam o estado inicial e
       o final
     - escolher um estado i que nao seja nem o estado inicial, nem o final
     - eliminar i da seguinte forma:
       para todo estado j, k que nao seja igual a e (incluindo j=k) faca:
       i) se w(j,i) not= vazio, w(i,k) not= vazio e w(i,i) = vazio
          entao crie um  arco de j para k com a expressao w(j,i).w(i,k)
       ii) se w(j,i) not= vazio, x(i,k) not= vazio e w(i,i) not= vazio
          entao crie um arco de j para k com a expressao w(j,i).w(i,i)*.w(i,k)
       iii) se os estados j e k tem arcos com expressoes w1,w2,...,ws 
          conectando-os 
          entao substitua-os por um unico arco w1+w2+...+ws
       iv) remova o estado i e todos os arcos incidentes em i
     
Exemplo1:




















Exemplo2: