AULA 3: CONJUNTOS REGULARES E EXPRESSOES REGULARES
==================================================

Def: As expressoes regulares sobre um alfabeto \Sigma e os conjuntos que
elas representam sao definidos recursivamente como:
   a) \emptyset e' uma expr. regular e representa o conjunto vazio
   b) \epsilon e' uma expr. regular e representa o conjunto {\emptyset}
   c) para cada 'a' em \Sigma, 'a' e' um expr. regular e representa
      o conjunto {a}
   d) se r e s sao expr. regulares que representam os conjuntos R e S,
      respectivamente, entao (r+s), (rs) e r* sao
      expr. regulares que representam os conjuntos R U S, R.S e R*,
      respectivamente. 

Exemplo: 
{bawab | w em {a,b}*}

    conjunto     expressao        justificativa

 1)   {a}           a                base
 2)   {b}           b                base
 3) {a}{b}          ab               1,2,concatenacao
 4) {a}U{b}         a+b              1,2,uniao
 5) {b}{a}          ba               1,2,concatenacao
 6) {a,b}*         (a+b)*            4,estrela Kleene
 7) {ba}{a,b}*     ba(a+b)*          5,6,concatenacao
 8) {ba}{a,b}*{ab} ba(a+b)*ab        7,3,concatenacao     

precedencia:  * . +
notacao:      r+ = rr*

Exemplos de linguagens sobre o alfabeto {0,1}:
 1) que contem 00
     (0+1)* 00 (0+1)*
 
 2) que contem 00 ou 11
     (0+1)* (00 + 11) (0+1)*
     (0+1)* 00 (0+1)* + (0+1)* 11 (0+1)*

 3) que contem exatamente dois 0's
     1* 0 1* 0 1*

 4) que contem dois ou mais 0's
     (0+1)* 0 (0+1)* 0 (0+1)*

 5) que contem numero par de 0's
     1* + (1* 0 1* 0 1*)*
     1* (0 1* 0 1*)*

 6) que nao contem o substring 00
        1*(01+)* + 1*(01+)*0
        (1 + 01)* (\epsilon + 0)

Identidades de expressoes:
-------------------------
1) vazio.u = u.vazio = vazio
2) \epsilon.u = u.\epsilon = u
3) vazio* = \epsilon
4) \epsilon* = \epsilon
5) u+v = v+u
6) u+vazio = u
7) u+u = u
8) u* = (u*)*
9) u(v+w) = uv + uw
10) (u+v)w = uw + vw
11) (uv)*u = u(vu)*
12) (u+v)* = (u* + v)*
           = u*(u+v)* = (u + vu*)*
           = (u*v*)*  = u*(vu*)*
           = (u*v)*u*