Регулярні множини та регулярні вирази

Означення: Нехай S - скінчений алфавіт. Регулярна множина в алфавіті S визначається рекурсивно:

П1. Æ - пуста множина – це регулярна множина в алфавіті S;

П2. {e} – пусте слово – регулярна множина в алфавіті S;

П3. {a} – однолітерна множина – регулярна множина в алфавіті S;

П4. Якщо P та Q – регулярні множини, то такими є наступні множини:

P È Q (операція об’єднання);

P * Q (операція конкатенації);

{P} = {e} È P È P*P È ……. (операція ітерації).

П5. Ніякі інші множини, окрім побудованих на основі ПП 1-4 не є регулярними множинами.

Таким чином, регулярні множини можна побудувати з базових елементів ПП 1-3 шляхом скінченого застосування операцій об’єднання, конкатенації та ітерації.

Регулярні вирази позначають регулярні множини таким чином, що:

П1. 0 позначає регулярну множину Æ;

П2. e позначає регулярну множину {e};

П3. а позначає регулярну множину {a};

П4. Якщо p та q позначають відповідно регулярні множини P та Q, то

p + q позначає регулярну множину P È Q;

p ^. p позначає регулярну множину P * Q;

p* позначає регулярну множину {P}.

П5. Ніякі інші вирази, окрім побудованих на основі ПП 1-4 не є регулярними виразами.

Оскільки ми почали вести мову про вирази, нам зручніше перейти до поняття алгебри регулярних виразів. Для кожної алгебри одним з важливих питань є питання тотожних перетворень, які виконуються на основі тотожностій в цій алгебрі. Сформулюємо основні тотожності алгебри регулярних виразів:

- a + b = b + a; 7) a + b + c = a + (b + c);

- ae = ea = a; 8) a + b + c = (a + b) + c;

- a0 = 0a = 0; 9) p + p* = p*;

- a(b + c) = ab + ac; 10) 0* = e;

- (a + b)c = ac + bc; 11) e* = e.

- a + a = a;

По аналогії з класичними алгебрами розглянемо лінійне рівняння в алгебрі регулярних виразів:

X = aX + b, де a, b – регулярні вирази.

Взагалі таке рівняння в залежності від a та b може мати безліч розв’язків, наприклад: X = a*(b + g), при умові, що a позначає e-ланцюжок. Тоді g може бути навіть і нерегулярним виразом. Серед всіляких розв’язків рівняння з регулярними коефіцієнтами виберемо найменший розв’язок X = a*b, який назвемо найменша нерухома точка. Щоб перевірити, що a*b розв’язок рівняння в алгебрі регулярних виразів, підставимо його в початкове рівняння та перевіримо тотожність виразів на основі системи тотожних перетворень:

a*b = aa*b+b = (aa*+e)b = (a (e + a +aa+…) + e)b = (e + a + aa +…)b = a*b

В алгебрі регулярних виразів також розглядають і системи лінійних рівнянь з регулярними коефіцієнтами:

X₁ = a₁₁X₁ + a₁₂X₂+ … + a_1nX_n + b₁

X₂ = a₂₁X₁ + a₂₂X₂+ … + a_2nX_n + b₂

………………..

X_n = a_1nX₁ + a_2nX₂ + … + a_nnX_n + b_n

де a_ij, b_i, i,j = 1..n.

Метод розв’язку системи лінійних рівнянь з регулярними коефіцієнтами нагадує метод виключення Гауса.

П1. Покласти i = 1.

П2. Якщо i рівне n, то перейти на П4. Інакше і–е рівняння, використавши систему тотожних перетворень, записати у вигляді:

X_i = aX_i + b, де a - регулярний вираз в алфавіті S, а b – регулярний вираз виду b₀ + b_i+1X_i+1 + b_i+2X_i+2 + … b_nX_n, де b_k (k=0, i+1,.. n) - регулярні коефіцієнти. Далі, в правих частинах рівнянь зі змінними X_i+1, X_i+2, … X_n в лівій частині рівняння підставити заміст X_i значення a*b.

П3. Збільшити i на 1 та перейти на П2.

П4. Записати рівняння X_n = aX_n + b, де a, b – регулярні вирази в алфавіті S. Це можливо оскільки на кожному кроці виконання П2 для кожного i < n в в правій частині рівняння для X_i не буде невідомих X₁, X₂, …, X_i-1. Перейти на П5, при цьому i буде рівне n.

П5. Для рівняння з X_i, котре має вигляд X_i = aX_i + b, де a, b - регулярні вирази в алфавіті S, записати X_i = a*b. В рівняння для X₁, X₂, …, X_i-1 підставити замість X_i регулярний вираз a*b.

П6. Якщо і рівне 1 то зупинитися, інакше i зменшити на 1 та перейти на П5.

Приклад 4. Розв'язати систему лінійних рівнянь:

X = a₁X + a₂Y + a₃

Y = b₁X + b₂Y +b₃

З першого рівняння:

X = a₁*(a₂Y + a₃).

Підставимо значення X в друге рівняння та зведемо подібні члени:

Y = b₁a₁*(a₂Y+a₃) + b₂Y + b₃ = b₁a₁*a₂Y + b₁a₁*a₃ + b₂Y+ b₃ =

(b₁a₁*a₂ + b₂)Y + (b₁a₁*a₃ + b₃)

Таким чином,

Y = (b₁a₁*a₂ + b₂)* (b₁a₁*a₃ + b₃).

Підставимо Y в перше рівняння:

X = a₁X + a₂(b₁a₁*a₂ + b₂)* (b₁a₁*a₃ + b₃) + a₃

Звідси,

X = a₁*(a₂(b₁a₁*a₂ + b₂)* (b₁a₁*a₃ + b₃) + a₃)