Регулярні вирази. Властивості регулярних виразів

Регулярні множини можна позначати за допомогою регулярних виразів. Ці позначення вводяться наступним чином:

1. О - регулярний вираз, що означає 0;

2. X - регулярний вираз, що означає {X};

3.а - регулярний вираз, що означає {a} VaeV;

4. якщо р і q - регулярні вирази, що позначають регулярні безлічі Р і Q, то р + q, pq, р * - регулярні вирази, що позначають регулярні мно ¬ дружність PuQ, PQ і Р * відповідно.

ПРИМІТКА

Іноді для зручності позначень вводять також операцію непорожній ітерації, кото ¬ рая позначається р + і для будь-якого регулярного вираження р справедливо: р + - рр * - Р * Р.

Два регулярних вислови аїр рівні а - р, якщо вони означають одне і те ж кількість.

Кожне регулярний вираз позначає те й лише регулярне мно ¬ дружність, але для одного регулярного безлічі може існувати як завгодно багато регулярних виразів, що позначають це безліч.

При запису регулярних виразів будуть використовуватися круглі дужки, як і для звичайних арифметичних виразів. При відсутності дужок операції виконуються зліва направо з урахуванням пріоритету.Пріоритет для операцій при ¬ Нят наступний: першим виконується ітерація (вищий пріоритет), потім кон ¬ катенація, потім - об'єднання множин (нижчий пріоритет). Якщо а, Р і в - регулярні вирази, то властивості регулярних виразів можна записати у вигляді наступних формул:

1.X + act '= X + а'а = а * (Я + а + - а ")

2. а + р = Р + АЗ

3. а + (р + у) - (а + Р) + у

4. а (Р + у) = ар + ау

5. (Р + у) а - ра + уа

6. а (Ру) - (аК) у

7. а + а - а

8. а + а * - а '

9. X + а - а * + X - а *

10. 0 *- Я.

11. Оа-АТ-0

12. О + а-а +0- а

13. Ха - аХ - а

14. (А ')' - а ".

Всі ці властивості можна легко довести, грунтуючись на теорії множин, так як регулярні вирази - це тільки позначення для відповідних множин.

Слід також звернути увагу на те, що серед інших властивостей відсутня рівність аК - Ра, тобто операція конкатенації не має властивість ком ¬ мутатівності. Це й не дивно, оскільки для цієї операції важливий поря ¬ док проходження символів.

Рівняння з регулярними коефіцієнтами

На основі регулярних виразів можна побудувати рівняння з регулярними коефіцієнтами [15, 22]. Найпростіші рівняння з регулярними коеффіціен ¬ тами будуть виглядати наступним чином:

X - аХ + р, Х = Ха + р,

де

a, peV * - регулярні вирази над алфавітом V, а змінна XeV. Рішеннями таких рівнянь будуть регулярні множини.Це означає, що якщо взяти регулярне безліч, що є рішенням рівняння, позначити його у вигляді відповідного регулярного вираження і підставити в рівняння, то отримаємо тотожне рівність. Два види запису рівнянь (правостороння

і лівостороння записи) пов'язані з тим, що для регулярних виразів опера ¬ ція конкатенації не має властивість комутативності, тому коефіцієнт ¬ ент можна записати як справа, так і зліва від змінної, і при цьому вийдуть різні рівняння. Обидві записи рівноправні.

Рішенням першого рівняння є безліч, позначене регулярним виразом а * р. Перевіримо це рішення, підставивши його в рівняння замість пере ¬ менной X:

аХ + р - а (а * Р) + g -6 (аа *) р + р -13 (аа) Р + Хр -5 (аа * + Х) р -1 а * р - X.

Над знаками рівності вказані номери властивостей регулярних виразів, кото ¬ риє були використані для виконання перетворень. Рішенням другого рівняння є безліч, позначене регулярним виразом Ра *.

Ха + р - (ра *) а + Р -6 Р (а а) + р -13 р (а'а) + РХ -4 Р (а * а + К) -1 р <х * - X.

ПРИМІТКА

З рівнянь з регулярними коефіцієнтами можна формувати систему рівнянь з регулярними коефіцієнтами. Система рівнянь з регулярними коефіцієнтами має вигляд (правостороння запис):

xi ~ «ю +« uXi + ai2X2 + ... + & InX "Х2 - аго + o ^ iXj + а22Х2 + ... + А ^ Х,,

X, - ai0 + а,, Х, + ai2X2 + ... + А ^ Х,,

Х "- + anlX, + а, 2Х2 +,. + Ал або (лівостороння запис): Xj - a, 0 '+ Xian + X2a, 2 + ... + Xnaln X2 - a2o + X | Ct2i + X2a22 + ... + X "a2n

Xj - al0 + X. Oj, + X2al2 + ... + Xna, n

X "- an0 + Xjd,,, + X2ai2 + ... + Xna "n.

В системі рівнянь з регулярними коефіцієнтами всі коефіцієнти а "є регулярними виразами над алфавітом V, а змінні не входять в алфавіт V: Vi Xj« V. Обидва варіанти запису рівноправні, але в загальному випадку мо ¬ жуть мати різні рішення при однакових коефіцієнтах при змінних.

Зазначені рішення рівнянь не завжди є єдиними. Однак доведено, що X - А'В і X - ра * - це найменші з можливих рішень для даних двох рівнянь. Ці рішення називаються найменшою рухомий точкою [4. т. 1, 15].

Крок 2.

Маємо i - 1 <4.

Беремо рівняння для i - 1. Маємо XI = ("-" + "+" + X). Це вже і є рішення для XI.

Підставляємо його в інші рівняння. Отримуємо:

Х2 - ("-» + • • + "+ я.)". "(О + 1) + Х3 \" + Х2 (0 + 1) ХЗ = ("-» + • • + "+ Х) (0 + 1) + Х3 (0 + 1) Х4 = Х2 + ХЗ

Крок 3.

i: - i + 1 - 2 Повертаємося до кроку 2.Крок 2.

Маємо i - 2 <4.

Беремо рівняння для i - 2. Маємо Х2 = ("-" + "+" + Я.) "." (О + 1) + ХЗ "." + Х2 (0 + 1). Перетворимо рівняння до виду: Х2 - Х2 (0 + 1) + (("-" + "+" + X )"."( О + 1) + ХЗ "."). Тоді а2 = (0 + 1), (32 = ("-" + "+ і + X )"."( О + 1) + ХЗ". ".Рішенням для Х2 буде: Х2 = Р2а2 * = (("-" + "+" + ХГ. 'ЧО + 1) + Х3 ".")( 0 + 1) * - ("-" + "+" + Х )"."( 0 + + 1) (0 + 1) * + Х3 "." (0 + 1) *. Підставимо його в інші рівняння. Отримуємо:

ХЗ = (»- • ■ + • ■ + ■ • + Х) (0 + 1) + Х3 (0 + 1)

Х4 = (• • - »+" + "+ я .)"."( 0 + 1) (0 + 1) * + Х3". "(0 + 1) * + ХЗ

Крок 3.

i: - i + 1 = 3 Повертаємося до кроку 2. Крок 2.

Маємо i = 3 <4.

Беремо рівняння для i - 3. Маємо ХЗ - ("-" + "+" + А.) (О + 1) + Х3 (0 + 1). Перетворень ¬ зуемих рівняння до виду ХЗ = Х3 (0 + 1) + ("-" + "+" + Х) (0 + 1). Тоді аз - (0 + 1). РЗ = (• • _ • • + • ■ + ■ ■ + Х) (0 + 1).Рішенням для ХЗ буде: ХЗ - рЗаЗ * - ("-" + "+" + X) (О + 1X0 + 1) *.

Підставимо його в інші рівняння. Отримуємо:

Х4 = ("-" + "+" + Х )"."( 0 + 1) (0 + 1) * + ("-" + "+" + ХХО + 1X0 + 1 )*"." а * + + ("-" + "+" + ХХО + 1X0 + 1) *.

ШагЗ.

1: - i + 1 - 4

Повертаємося до кроку 2. Крок 2.

Маємо i = 4 = 4.Переходимо до кроку 4.

Крок 4.

Рівняння для Х4 тепер має вигляд Х4 - ("-" + "+" + А ,)"."( О + 1) (0 + 1) * + ("-" + "+ ■ ■ + Х) (0 + 1) (0 + 1 )*"."( 0 + 1) * + ("-" + "+" + Я.) (0 + 1) (0 + 1) *. Воно не потребує перетвореннях і містить остаточне рішення для Х4.Переходимо до кроку 5. Крок 5.

i: = i - 1 = 3> Про Переходимо до кроку 6. Крок 6.

Рівняння для ХЗ має вигляд ХЗ = ("-" + "+" + Х) (0 + 1) (0 + 1) *. Воно вже містить остаточне рішення для ХЗ. Переходимо до кроку 5.

Крок 5.

i: - i - 1 - 2> Про Переходимо до кроку 6. Крок 6.

Рівняння для Х2 має вигляд Х2 = ("-" + "+" + X) "." Аа * + ХЗ "." А *. Підставимо в нього остаточне рішення для Х3. Отримаємо остаточне рішення для Х2: Х2 = (»- '■ + + ЛГ." (О + 1) (0 + 1) * + ("-" + "+" + л-КО + 1) (0 + 1) *"."( 0 + 1) *. Переходимо до кроку 5.

Крок 5.

i: = i - 1 - 1> Про Переходимо до кроку 6.Крок 6.

Рівняння для XI має вигляд XI = ("-" + "+" + X). Воно вже містить остаточний ¬ ве рішення для XI. Переходимо до кроку 5.

Крок 5.

i: - i - 1 - 0 - Про

Алгоритм завершений.

В результаті отримали рішення:

XI = ("." + "+ ■ ■ + х)

Х2 = ("-" + "+" + х )"."( 0 + 1) (0 + 1) * + ("-" + "+" + Л) (0 + 1) (0 + 1) * "."(0 + 1) * ХЗ = (• • _" + • • + ■ ■ + х) (0 + 1) (0 + 1) *

Х4 = ("-" + ■ • + »+ х )"."( 0 + 1) (0 + 1) * + (" - "+" + "+ Х) (0 + 1) (0 + 1) *"."( 0 + 1) * + (»_ • • + ■ ■ + ■ '+ х) (0 + 1) (0 + 1) *

Виконавши нескладні перетворення, це ж рішення можна представити в бо ¬ леї простому вигляді:

XI = (• ■ _ »+ • • +" + К)

Х2 = ("-" + "+" + х ,)("."( 0 + 1) + (0 + 1) (0 + 1 )*".")( 0 + 1) *

ХЗ = (■ ■ _ ■ '+ + Х) (0 + 1) +

Х4 = ("-" + • '+ ■ • + х ,)("."( 0 + 1) + (0 + 1) (0 + 1 )*"." + (0 + 1)) (0 + 1) * '

Можна помітити, що регулярне вираження для Х4 описує мова двійкових чисел з плаваючою крапкою.