Любой набор, представляющий значение регулярного выражения, называется регулярным набором.
Свойства регулярных множеств
Свойство 1 . Объединение двух регулярных множеств является регулярным.
Доказательство —
Давайте возьмем два регулярных выражения
RE 1 = a (aa) * и RE 2 = (aa) *
Итак, L 1 = {a, aaa, aaaaa, …..} (строки нечетной длины, исключая Null)
и L 2 = {ε, aa, aaaa, aaaaaa, …….} (строки четной длины, включая ноль)
L 1 ∪ L 2 = {ε, a, aa, aaa, aaaa, aaaaa, aaaaaa, …….}
(Строки всех возможных длин, включая Null)
RE (L 1 ∪ L 2 ) = a * (что само является регулярным выражением)
Следовательно, доказано.
Свойство 2. Пересечение двух регулярных множеств регулярно.
Доказательство —
Давайте возьмем два регулярных выражения
RE 1 = a (a *) и RE 2 = (aa) *
Итак, L 1 = {a, aa, aaa, aaaa, ….} (строки любой возможной длины, кроме Null)
L 2 = {ε, aa, aaaa, aaaaaa, …….} (строки четной длины, включая ноль)
L 1 ∩ L 2 = {aa, aaaa, aaaaaa, …….} (строки четной длины, исключая Null)
RE (L 1 ∩ L 2 ) = aa (aa) *, что само является регулярным выражением.
Следовательно, доказано.
Свойство 3. Дополнение регулярного множества регулярно.
Доказательство —
Давайте возьмем регулярное выражение —
RE = (аа) *
Итак, L = {ε, aa, aaaa, aaaaaa, …….} (строки четной длины, включая ноль)
Дополнением к L являются все строки, которых нет в L.
Итак, L ‘= {a, aaa, aaaaa, …..} (строки нечетной длины, исключая Null)
RE (L ‘) = a (aa) *, которая сама является регулярным выражением.
Следовательно, доказано.
Свойство 4. Разница двух регулярных множеств регулярна.
Доказательство —
Давайте возьмем два регулярных выражения —
RE 1 = a (a *) и RE 2 = (aa) *
Итак, L 1 = {a, aa, aaa, aaaa, ….} (строки любой возможной длины, кроме Null)
L 2 = {ε, aa, aaaa, aaaaaa, …….} (строки четной длины, включая ноль)
L 1 — L 2 = {а, ааа, ааааа, ааааааа, ….}
(Строки всех нечетных длин, кроме Null)
RE (L 1 — L 2 ) = a (aa) *, что является регулярным выражением.
Следовательно, доказано.
Свойство 5. Обращение регулярного множества регулярно.
Доказательство —
Мы должны доказать, что L R также регулярно, если 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, что регулярно
Следовательно, доказано.
Свойство 6. Закрытие регулярного множества регулярно.
Доказательство —
Если L = {a, aaa, aaaaa, …….} (строки нечетной длины, исключая Null)
то есть RE (L) = a (aa) *
L * = {a, aa, aaa, aaaa, aaaaa, ……………} (строки любой длины, кроме Null)
RE (L *) = a (a) *
Следовательно, доказано.
Свойство 7. Конкатенация двух регулярных множеств регулярна.
Доказательство —
Пусть 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, ………….}
Набор строк, содержащих 001 в качестве подстроки, которая может быть представлена RE — (0 + 1) * 001 (0 + 1) *
Следовательно, доказано.
Тождества, связанные с регулярными выражениями
Учитывая R, P, L, Q как регулярные выражения, справедливы следующие тождества: