Automata-theory-regular-sets
レギュラーセット
正規表現の値を表すすべてのセットは、*正規セット*と呼ばれます
レギュラーセットのプロパティ
- プロパティ1 *。 2つの正規セットの和集合は正規です。
証明-
2つの正規表現を使用してみましょう
RE〜1〜= a（aa）*およびRE〜2〜=（aa） *
したがって、L〜1〜= \ {a、aaa、aaaaa、…..}（Nullを除く奇数長の文字列）
およびL〜2〜= \ {ε、aa、aaaa、aaaaaa、…….}（Nullを含む偶数の文字列）
L〜1〜∪L〜2〜= \ {ε、a、aa、aaa、aaaa、aaaaa、aaaaaa、…….}
（Nullを含むすべての可能な長さの文字列）
RE（L〜1〜∪L〜2〜）= a* （それ自体が正規表現です）
したがって、証明。
- プロパティ2. * 2つのレギュラーセットの共通部分はレギュラーです。
証明-
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）*これは正規表現そのものです。
したがって、証明。
- プロパティ3. * レギュラーセットの補数はレギュラーです。
証明-
正規表現を取りましょう-
RE =（aa）*
したがって、L = \ {ε、aa、aaaa、aaaaaa、…….}（Nullを含む偶数の文字列）
*L* の補数は、 *L* にないすべての文字列です。したがって、L ’= \ {a、aaa、aaaaa、…..}（Nullを除く奇数長の文字列）
RE（L ’）= a（aa）*これはそれ自体が正規表現です。
したがって、証明。
- プロパティ4. * 2つのレギュラーセットの違いはレギュラーです。
証明-
私たちは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、aaaaa、aaaaaaa、….}
（ヌルを除くすべての奇数長のストリング）
RE（L〜1〜– L〜2〜）= a（aa）*これは正規表現です。
したがって、証明。
- プロパティ5. * レギュラーセットの反転はレギュラーです。
証明-
*L* が正規集合の場合、 *L ^ R ^* も正規であることを証明する必要があります。みましょう、L = \ {01、10、11、10}
RE（L）= 01 + 10 + 11 + 10
L ^ R ^ = \ {10、01、11、01}
RE（L ^ R ^）= 01 + 10 + 11 + 10（通常）
したがって、証明。
- プロパティ6. * 通常のセットのクローズは通常です。
証明-
L = \ {a、aaa、aaaaa、…….}（Nullを除く奇数長の文字列）の場合
すなわち、RE（L）= a（aa） *
L* = \ {a、aa、aaa、aaaa、aaaaa、……………}（Nullを除くすべての長さの文字列）
RE（L ）= a（a）
したがって、証明。
- プロパティ7. * 2つの正規セットの連結は正規です。
証明-
RE〜1〜=（0 + 1）* 0およびRE〜2〜= 01（0 + 1）*とする
ここで、L〜1〜= \ {0、00、10、000、010、……}（0で終わる文字列のセット）
およびL〜2〜= \ {01、010,011、…..}（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
