Set regolari

Qualsiasi insieme che rappresenta il valore dell'espressione regolare è chiamato a Regular Set.

Proprietà degli insiemi regolari

Property 1. L'unione di due serie regolare è regolare.

Proof -

Prendiamo due espressioni regolari

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

Quindi, L 1 = {a, aaa, aaaaa, .....} (stringhe di lunghezza dispari escluso Null)

e L 2 = {ε, aa, aaaa, aaaaaa, .......} (stringhe di lunghezza pari incluso Null)

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

(Stringhe di tutte le lunghezze possibili incluso Null)

RE (L 1 ∪ L 2 ) = a * (che è essa stessa un'espressione regolare)

Hence, proved.

Property 2. L'intersezione di due serie regolari è regolare.

Proof -

Prendiamo due espressioni regolari

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

Quindi, L 1 = {a, aa, aaa, aaaa, ....} (stringhe di tutte le lunghezze possibili escluso Null)

L 2 = {ε, aa, aaaa, aaaaaa, .......} (stringhe di lunghezza pari incluso Null)

L 1 ∩ L 2 = {aa, aaaa, aaaaaa, .......} (stringhe di lunghezza pari escluso Null)

RE (L 1 ∩ L 2 ) = aa (aa) * che è essa stessa un'espressione regolare.

Hence, proved.

Property 3. Il complemento di un set regolare è regolare.

Proof -

Prendiamo un'espressione regolare:

RE = (aa) *

Quindi, L = {ε, aa, aaaa, aaaaaa, .......} (stringhe di lunghezza pari incluso Null)

Complemento di L sono tutte le stringhe che non sono in L.

Quindi, L '= {a, aaa, aaaaa, .....} (stringhe di lunghezza dispari escluso Null)

RE (L ') = a (aa) * che è essa stessa un'espressione regolare.

Hence, proved.

Property 4. La differenza di due set regolari è regolare.

Proof -

Prendiamo due espressioni regolari:

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

Quindi, L 1 = {a, aa, aaa, aaaa, ....} (stringhe di tutte le lunghezze possibili escluso Null)

L 2 = {ε, aa, aaaa, aaaaaa, .......} (stringhe di lunghezza pari incluso Null)

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

(Stringhe di tutte le lunghezze dispari escluso Null)

RE (L 1 - L 2 ) = a (aa) * che è un'espressione regolare.

Hence, proved.

Property 5. L'inversione di una serie regolare è regolare.

Proof -

Dobbiamo provare LR è regolare anche se L è un set regolare.

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

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

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

RE (L R ) = 01 + 10 + 11 + 10 che è regolare

Hence, proved.

Property 6. La chiusura di una serie regolare è regolare.

Proof -

Se L = {a, aaa, aaaaa, .......} (stringhe di lunghezza dispari escluso Null)

cioè, RE (L) = a (aa) *

L * = {a, aa, aaa, aaaa, aaaaa, ……………} (stringhe di tutte le lunghezze escluso Null)

RE (L *) = a (a) *

Hence, proved.

Property 7. La concatenazione di due insiemi regolari è regolare.

Proof −

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

Qui, L 1 = {0, 00, 10, 000, 010, ......} (Set di stringhe che terminano con 0)

e L 2 = {01, 010,011, .....} (insieme di stringhe che iniziano con 01)

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

Insieme di stringhe contenenti 001 come sottostringa che può essere rappresentata da un RE - (0 + 1) * 001 (0 + 1) *

Quindi, dimostrato.

Identità correlate alle espressioni regolari

Dato R, P, L, Q come espressioni regolari, valgono le seguenti identità:

  • ∅ * = ε
  • ε * = ε
  • 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 (L'identità per l'unione)
  • R ε = ε R = R (L'identità per la concatenazione)
  • ∅ L = L ∅ = ∅ (L'annichilatore per la concatenazione)
  • R + R = R (legge idempotente)
  • L (M + N) = LM + LN (Legge distributiva sinistra)
  • (M + N) L = ML + NL (Diritto distributivo destro)
  • ε + RR * = ε + R * R = R *