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 *