Зміст:
Регулярні множини
Нехай \(\Sigma\) — скінчений алфавіт. Регулярна множина в алфавіті \(\Sigma\) визначається рекурсивно:
-
\(\varnothing\) — пуста множина — це регулярна множина в алфавіті \(\Sigma\);
-
\(\{\varepsilon\}\) — пусте слово — регулярна множина в алфавіті \(\Sigma\);
-
\(\{a\}\) — однолітерна множина — регулярна множина в алфавіті \(\Sigma\);
-
Якщо \(P\) та \(Q\) — регулярні множини, то такими є наступні множини:
-
\(P \cup Q\) (операція об’єднання);
-
\(P \times Q\) (операція конкатенації);
-
\(P^\star = \{\varepsilon\} \cup P \cup P^2 \cup \ldots\) (операція ітерації).
-
-
Ніякі інші множини, окрім побудованих на основі 1–4 не є регулярними множинами.
Таким чином, регулярні множини можна побудувати з базових елементів 1-3 шляхом скінченого застосування операцій об’єднання, конкатенації та ітерації.
Регулярні вирази
Регулярні вирази позначають регулярні множини таким чином, що:
-
\(0\) позначає регулярну множину \(\varnothing\);
-
\(\varepsilon\) позначає регулярну множину \(\{\varepsilon\}\);
-
\(a\) позначає регулярну множину \(\{a\}\);
-
Якщо \(p\) та \(q\) позначають відповідно регулярні множини \(P\) та \(Q\), то
-
\(p + q\) позначає регулярну множину \(P \cup Q\);
-
\(p \cdot q\) позначає регулярну множину \(P \times Q\);
-
\(p^\star\) позначає регулярну множину \(P^\star\).
-
-
Ніякі інші вирази, окрім побудованих на основі 1–4 не є регулярними виразами.
Алгебра регулярних виразів
Оскільки ми почали вести мову про вирази, нам зручніше перейти до поняття алгебри регулярних виразів. Для кожної алгебри одним з важливих питань є питання еквівалентних перетворень, які виконуються на основі тотожностей у цій алгебрі. Сформулюємо основні тотожності алгебри регулярних виразів:
-
\(a + b + c = a + (b + c)\) (ліва асоціативність додавання);
-
\(a + b + c = (a + b) + c\) (права асоціативність додавання);
-
\(a + 0 = 0 + a = a\) (\(0\) — нейтральний елемент за додаванням);
-
\(a \cdot b \cdot c = a \cdot (b \cdot c)\) (ліва асоціативність множення);
-
\(a \cdot b \cdot c = (a \cdot b) \cdot c\) (права асоціативність множення);
-
\(a + b = b + a\) (комутативність додавання);
-
\(a \cdot \varepsilon = \varepsilon \cdot a = a\) (\(\varepsilon\) — нейтральний елемент за множенням);
-
\(a \cdot 0 = 0 \cdot a = 0\) (\(0\) — нульовий елемент за множенням);
-
\(a \cdot (b + c) = a \cdot b + a \cdot c\) (ліва дистрибутивність множення відносно додавання);
-
\((a + b) \cdot c = a \cdot c + b \cdot c\) (права дистрибутивність множення відносно додавання).
У алгебри регулярних виразів є і некласичні властивості:
-
\(a + a = a\);
-
\(p + p^\star = p^\star\);
-
\(0^\star = \varepsilon\);
-
\(\varepsilon^\star = \varepsilon\).
Лінійні рівняння
За аналогією з класичними алгебрами розглянемо лінійне рівняння в алгебрі регулярних виразів: \(X = a \cdot X + b\), де \(a\), \(b\) — регулярні вирази.
Взагалі кажучи таке рівняння (в залежності від \(a\) та \(b\)) може мати безліч розв’язків.
Серед всіх розв’язків рівняння з регулярними коефіцієнтами виберемо найменший розв’язок \(X = a^\star \cdot b\), який назвемо найменша нерухома точка.
Щоб перевірити, що \(a^\star \cdot b\) справді розв’язок рівняння в алгебрі регулярних виразів, підставимо його в початкове рівняння та перевіримо тотожність виразів на основі системи тотожних перетворень:
\[a^\star b = a a^\star b = (a a^\star + \varepsilon) b = (a (\varepsilon + a + a^2 + \ldots ) + \varepsilon) b = (\varepsilon a + a^2 + \ldots) b = a^\star b.\]Системи рівнянь
В алгебрі регулярних виразів також розглядають і системи лінійних рівнянь з регулярними коефіцієнтами:
\[\left\{ \begin{aligned} X_1 &= a_{11} X_1 + a_{12} X_2 + \ldots + a_{1n} X_n + b_1, \\ X_2 &= a_{21} X_1 + a_{22} X_2 + \ldots + a_{2n} X_n + b_2, \\ &\ldots \\ X_n &= a_{n1} X_1 + a_{n2} X_2 + \ldots + a_{nn} X_n + b_n. \end{aligned} \right.\]Метод розв’язування системи лінійних рівнянь з регулярними коефіцієнтами нагадує метод виключення Гауса.
-
Для \(i = \overline{1..n}\), використавши систему тотожних перетворень, записати \(i\)-е рівняння у вигляді: \(X_i = a X_i + b\), де \(a\) — регулярний вираз в алфавіті \(\Sigma\), а \(b\) — регулярний вираз виду
\[\beta_0 + \beta_{i+1} X_{i+1} + \beta_{i+2} X_{i+2} + \ldots + \beta_n X_n,\]де \(\beta_k\) (\(k = 0, \overline{i+1..n}\)) — регулярні коефіцієнти. Далі, в правих частинах рівнянь зі змінними \(X_{i+1}, X_{i+2}, \ldots, X_n\) в лівій частині рівняння підставити замість \(X_i\) значення \(a^\star b\).
-
Для \(i = \overline{n..1}\) розв’язати \(i\)-е рівняння яке зараз має вигляд \(X_i = a X_i + b\), де \(a\), \(b\) — регулярні вирази в алфавіті \(\Sigma\), і підставити його розв’язок \(a^\star b\) у коефіцієнти рівнянь зі змінними \(X_{i-1}, X_{i-2}, \ldots, X_1\).
Приклад. Розв’язати систему \(2\times2\):
\[\left\{ \begin{aligned} X_1 &= a_{11} X_1 + a_{12} X_2 + b_1, \\ X_2 &= a_{21} X_1 + a_{22} X_2 + b_2. \end{aligned} \right.\]Розв’язок:
-
З першого рівняння
\[X_1 = a_{11}^\star (a_{12} X_2 + b_1).\] -
Підставляємо у друге рівняння, воно набуває вигляду
\[X_2 = a_{21} (a_{11}^\star (a_{12} X_2 + b_1)) + a_{22} X_2 + b_2.\]Або, після спрощень:
\[X_2 = (a_{21} a_{11}^\star a_{12} + a_{22}) X_2 + (a_{21} a_{11}^\star b_1 + b_2).\]Звідки знаходимо:
\[X_2 = (a_{21} a_{11}^\star a_{12} + a_{22})^\star (a_{21} a_{11}^\star b_1 + b_2).\] -
Підставляємо у вираз для \(X_1\):
\[X_1 = a_{11}^\star (a_{12} (a_{21} a_{11}^\star a_{12} + a_{22})^\star (a_{21} a_{11}^\star b_1 + b_2) + b_1).\]Тут можна розкрити дужки, але зараз у цьому немає потреби.
Контрольні запитання
-
Яка множина називається регулярною (в алфавіті \(\Sigma\))?
-
Як регулярні вирази позначаються регулярні множини?
-
Які класичні тотожності алгебри регулярних виразів ви знаєте?
-
Які не класичні тотожності алгебри регулярних виразів ви знаєте?
-
Який розв’язок лінійного рівняння \(X = a \cdot X + b\) називається найменшою нерухомою точкою?
-
Доведіть, що згаданий у попередньому рівняння вираз справді є розв’язком.
-
Сформулюйте алгоритм Гауса розв’язування систем лінійних регулярних рівнянь.
-
Розв’яжіть систему \(3\times3\):
\[\left\{ \begin{aligned} X_1 &= a X_1 + b X_2 + c, \\ X_2 &= c X_1 + a X_2 + b X_3, \\ X_3 &= b + c X_2 + a X_3. \end{aligned} \right.\]
(традиційні відповіді можна переглянути у коментарях у вихідному коді цієї сторінки)