レギュラーセット

正規表現の値を表すセットは、 Regular Set.

通常のセットのプロパティ

Property 12つの通常のセットの和集合は通常です。

Proof

2つの正規表現を取りましょう

RE 1 = a(aa)*およびRE 2 =(aa)*

したがって、L 1 = {a、aaa、aaaaa、.....}(Nullを除く奇数の長さの文字列)

そして L 2 = {ε、AA、AAAA、AAAAAA、.......}(NULLを含む偶数長さの文字列)

L 1 ∪L 2 = {ε、AA、AAA、AAAA、AAAAA、AAAAAA、.......}

(Nullを含むすべての可能な長さの文字列)

RE(L 1 ∪L 2)= * (正規表現自体です)

Hence, proved.

Property 2. 2つの通常のセットの交差は通常です。

Proof

2つの正規表現を取りましょう

RE 1 = a(a *)およびRE 2 =(aa)*

したがって、L 1 = {a、aa、aaa、aaaa、....}(Nullを除くすべての可能な長さの文字列)

L 2 = {ε、aa、aaaa、aaaaaa、.......}(Nullを含む偶数の長さの文字列)

L 1 ∩L 2 = {AA、AAAA、AAAAAA、.......}(NULLを除く偶数長さの文字列)

RE(L 1 ∩L 2正規表現そのものである)= AA(AA)*。

Hence, proved.

Property 3. 通常のセットの補集合は通常です。

Proof

正規表現を取りましょう-

RE =(aa)*

したがって、L = {ε、aa、aaaa、aaaaaa、.......}(Nullを含む偶数の長さの文字列)

の補数 L にないすべての文字列です L

したがって、L '= {a、aaa、aaaaa、.....}(Nullを除く奇数の長さの文字列)

RE(L ')= a(aa)*これは正規表現そのものです。

Hence, proved.

Property 4. 2つのレギュラーセットの違いはレギュラーです。

Proof

2つの正規表現を取りましょう-

RE 1 = a(a *)およびRE 2 =(aa)*

したがって、L 1 = {a、aa、aaa、aaaa、....}(Nullを除くすべての可能な長さの文字列)

L 2 = {ε、aa、aaaa、aaaaaa、.......}(Nullを含む偶数の長さの文字列)

L 1 – L 2 = {a、aaa、aaaaaa、aaaaaaa、....}

(Nullを除くすべての奇数の長さの文字列)

RE(L 1 – L 2)= a(aa)*これは正規表現です。

Hence, proved.

Property 5. 通常のセットの逆転は定期的です。

Proof

私たちは証明しなければなりません LR 次の場合も定期的です L レギュラーセットです。

、聞かせてL = {01、10、11、10}

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

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

RE(L R)= 01 + 10 + 11 +10これは通常です

Hence, proved.

Property 6. 通常のセットの閉鎖は定期的です。

Proof

L = {a、aaa、aaaaa、.......}の場合(Nullを除く奇数の長さの文字列)

つまり、RE(L)= a(aa)*

L * = {a、aa、aaa、aaaa、aaaaa、……………} (Nullを除くすべての長さの文字列)

RE(L *)= a(a)*

Hence, proved.

Property 7. 2つの通常のセットの連結は通常です。

Proof −

LET RE 1 =(0 + 1)* 0及びRE 2 = 01(0 + 1)*

ここで、L 1 = {0、00、10、000、010、......} (0で終わる文字列のセット)

そしてL 2 = {01、010011、...} (01から始まる文字列のセット)

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

RE −(0 + 1)* 001(0 + 1)*で表すことができる部分文字列として001を含む文字列のセット

したがって、証明されました。

正規表現に関連するID

正規表現としてR、P、L、Qが与えられると、次の恒等式が成り立ちます。

  • ∅* =ε
  • ε* =ε
  • 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 (結合の単位元)
  • Rε=εR= R (連結の単位元)
  • ∅L=L∅=∅ (連結の消滅子)
  • R + R = R (べき等法)
  • L(M + N)= LM + LN (左分配法則)
  • (M + N)L = ML + NL (右分配法則)
  • ε+ RR * =ε+ R * R = R *