Conjuntos regulares

Qualquer conjunto que representa o valor da Expressão Regular é chamado de Regular Set.

Propriedades de conjuntos regulares

Property 1. A união de dois conjuntos regulares é regular.

Proof -

Vamos pegar duas expressões regulares

RE 1 = a (aa) * e RE 2 = (aa) *

Então, L 1 = {a, aaa, aaaaa, .....} (Strings de comprimento ímpar excluindo Null)

e L 2 = {ε, aa, aaaa, aaaaaa, .......} (cordas de comprimento par incluindo nulo)

L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, .......}

(Strings de todos os comprimentos possíveis incluindo Null)

RE (L 1 ∪ L 2 ) = a * (que é uma expressão regular em si)

Hence, proved.

Property 2. A intersecção de dois conjuntos regulares é regular.

Proof -

Vamos pegar duas expressões regulares

RE 1 = a (a *) e RE 2 = (aa) *

Então, L 1 = {a, aa, aaa, aaaa, ....} (Strings de todos os comprimentos possíveis, exceto Null)

L 2 = {ε, aa, aaaa, aaaaaa, .......} (cordas de comprimento par incluindo nulo)

L 1 ∩ L 2 = {aa, aaaa, aaaaaa, .......} (Strings de comprimento par excluindo Null)

RE (L 1 ∩ L 2 ) = aa (aa) * que é a própria expressão regular.

Hence, proved.

Property 3. O complemento de um conjunto regular é regular.

Proof -

Tomemos uma expressão regular -

RE = (aa) *

Então, L = {ε, aa, aaaa, aaaaaa, .......} (Strings de comprimento par incluindo Null)

Complemento de L são todas as cordas que não estão em L.

Então, L '= {a, aaa, aaaaa, .....} (Strings de comprimento ímpar excluindo Null)

RE (L ') = a (aa) * que é uma expressão regular em si.

Hence, proved.

Property 4. A diferença de dois conjuntos regulares é regular.

Proof -

Tomemos duas expressões regulares -

RE 1 = a (a *) e RE 2 = (aa) *

Então, L 1 = {a, aa, aaa, aaaa, ....} (Strings de todos os comprimentos possíveis, exceto Null)

L 2 = {ε, aa, aaaa, aaaaaa, .......} (cordas de comprimento par incluindo nulo)

L 1 - L 2 = {a, aaa, aaaaa, aaaaaaa, ....}

(Strings de todos os comprimentos ímpares, exceto Null)

RE (L 1 - L 2 ) = a (aa) * que é uma expressão regular.

Hence, proved.

Property 5. A reversão de um conjunto regular é regular.

Proof -

Temos que provar LR também é regular se L é um conjunto regular.

Deixe, L = {01, 10, 11, 10}

RE (L) = 01 + 10 + 11 + 10

L R = {10, 01, 11, 01}

RE (L R ) = 01 + 10 + 11 + 10 que é regular

Hence, proved.

Property 6. O fechamento de um conjunto regular é regular.

Proof -

Se L = {a, aaa, aaaaa, .......} (Strings de comprimento ímpar excluindo Null)

ou seja, RE (L) = a (aa) *

L * = {a, aa, aaa, aaaa, aaaaa, ……………} (cordas de todos os comprimentos, exceto nulo)

RE (L *) = a (a) *

Hence, proved.

Property 7. A concatenação de dois conjuntos regulares é regular.

Proof −

Seja RE 1 = (0 + 1) * 0 e RE 2 = 01 (0 + 1) *

Aqui, L 1 = {0, 00, 10, 000, 010, ......} (conjunto de strings terminando em 0)

e L 2 = {01, 010.011, .....} (conjunto de strings começando com 01)

Então, L 1 L 2 = {001,0010,0011,0001,00010,00011,1001,10010, .............}

Conjunto de strings contendo 001 como substring que pode ser representado por um RE - (0 + 1) * 001 (0 + 1) *

Portanto, provado.

Identidades relacionadas a expressões regulares

Dado R, P, L, Q como expressões regulares, as seguintes identidades mantêm -

  • ∅ * = ε
  • ε * = ε
  • RR * = R * R
  • R * R * = R *
  • (R *) * = R *
  • RR * = R * R
  • (PQ) * P = P (QP) *
  • (a + b) * = (a * b *) * = (a * + b *) * = (a + b *) * = a * (ba *) *
  • R + ∅ = ∅ + R = R (a identidade para a união)
  • R ε = ε R = R (a identidade para concatenação)
  • ∅ L = L ∅ = ∅ (O aniquilador para concatenação)
  • R + R = R (lei idempotente)
  • L (M + N) = LM + LN (lei distributiva à esquerda)
  • (M + N) L = ML + NL (lei distributiva direita)
  • ε + RR * = ε + R * R = R *