Решение уравнений в регулярных выражениях — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
== Уравнения в регулярных выражениях ==
 
== Уравнения в регулярных выражениях ==
 
Поскольку алгебра [[Регулярные языки: два определения и их эквивалентность | регулярных выражений]] является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в [[Теория формальных языков | теории формальных языков]], но также была применена к алгоритмам поиска пути в графах<ref>[http://www.researchgate.net/publication/223558454_Regular_algebra_applied_to_language_problems/links/00b7d52caa66919923000000.pdf R.C. Backhouse, B.A. Carre: ''Regular algebra applied to path-finding problems''. J. Institute of Mathematics and its applications '''15''', 161-186 (1975)]</ref>, нахождения выпуклой оболочки<ref>[http://oai.cwi.nl/oai/asset/5015/05015D.pdf K. Clenaghan: ''Calculational graph algorithmics: reconciling two approaches with dynamic algebra''. CWI Amsterdam, Report CS-R9518, 1995]</ref>. В компиляторах она может быть использована для доказательства корректности методик оптимизации циклов<ref>[http://www.cs.cornell.edu/~kozen/papers/opti.pdf M.C. Patron, D. Kozen: ''Certification of compiler optimizations using Kleene algebra with tests'', Report 99-1779, Computer Science Department, Cornell University, Dec. 1999.]</ref>.
 
Поскольку алгебра [[Регулярные языки: два определения и их эквивалентность | регулярных выражений]] является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в [[Теория формальных языков | теории формальных языков]], но также была применена к алгоритмам поиска пути в графах<ref>[http://www.researchgate.net/publication/223558454_Regular_algebra_applied_to_language_problems/links/00b7d52caa66919923000000.pdf R.C. Backhouse, B.A. Carre: ''Regular algebra applied to path-finding problems''. J. Institute of Mathematics and its applications '''15''', 161-186 (1975)]</ref>, нахождения выпуклой оболочки<ref>[http://oai.cwi.nl/oai/asset/5015/05015D.pdf K. Clenaghan: ''Calculational graph algorithmics: reconciling two approaches with dynamic algebra''. CWI Amsterdam, Report CS-R9518, 1995]</ref>. В компиляторах она может быть использована для доказательства корректности методик оптимизации циклов<ref>[http://www.cs.cornell.edu/~kozen/papers/opti.pdf M.C. Patron, D. Kozen: ''Certification of compiler optimizations using Kleene algebra with tests'', Report 99-1779, Computer Science Department, Cornell University, Dec. 1999.]</ref>.

Текущая версия на 19:18, 4 сентября 2022

Уравнения в регулярных выражениях

Поскольку алгебра регулярных выражений является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в теории формальных языков, но также была применена к алгоритмам поиска пути в графах[1], нахождения выпуклой оболочки[2]. В компиляторах она может быть использована для доказательства корректности методик оптимизации циклов[3].

Решение уравнений в регулярных выражениях

Пусть [math]X[/math] — некий язык, для которого выполняется равенство [math]X = \alpha X + \beta [/math], где [math]\alpha,\,\beta[/math] — некие регулярные выражения над неким алфавитом [math]A[/math].

Утверждение:
Пусть уравнение имеет вид [math] X = \alpha X + \beta \Rightarrow \, 1)[/math] если [math]\varepsilon \notin \alpha [/math], тогда [math] \alpha^{*} \beta[/math] — единственное решение [math]2)[/math] если [math]\varepsilon \in \alpha [/math], тогда [math] \alpha^{*}( \beta + L)[/math] — решение для [math]\forall L[/math]
[math]\triangleright[/math]

[math] 1) [/math] Пусть [math]\varepsilon \notin \alpha [/math]. Тогда [math]\forall i \geqslant 0: [/math] выражение [math]\alpha^{i} \beta \subset X [/math], следовательно [math] \alpha^{*} \beta \subset X [/math]. Докажем это индукцией по [math]i[/math]: при [math]i = 0[/math] из начального равенства [math]\beta \subset X[/math], и если [math]\alpha^{i} \beta \subset X[/math], то [math]\alpha^{i+1} \beta = \alpha \alpha^{i} \beta \subset \alpha X \subset X[/math].

Пусть существует [math] z \in X,\, z\notin \alpha^{*} \beta[/math] такой, что [math] z [/math] — самое короткое; тогда [math]z \notin \beta \subset \alpha^{*} \beta \Rightarrow z \in \alpha X, z=z_\alpha z', [/math] где [math]z_\alpha \in \alpha, z' \in X, z' \notin \alpha^{*} \beta [/math].

Тогда [math] z_\alpha \ne \varepsilon \Rightarrow z'[/math] короче [math]z[/math], противоречие, тогда не существует самого короткого [math]z[/math], значит не существует никакого.


[math] 2)[/math] Пусть [math] \varepsilon \in \alpha[/math]. Тогда можно представить этот язык в виде [math]\alpha = \varepsilon + \alpha_{1}, \varepsilon \notin \alpha_{1}[/math], а исходное равенство преобразуется в [math]\varepsilon X + \alpha_{1} X + \beta = X[/math]. Теперь мы можем взять в качестве базы индукции не просто [math]\beta[/math], а любой язык [math]L \supset \beta[/math], или, что то же самое, любой [math]\beta + L[/math], и дальше показать [math]\forall i \geqslant 0: {\alpha_{1}}^{i} (\beta + L) \subset X \Rightarrow {\alpha_{1}}^{*} (\beta + L) \subset X[/math], а потом отсутствие самого короткого [math]z \in X, z \notin {\alpha_{1}}^{*}(\beta + L)[/math]. Заметим, что [math]\alpha^{*}={\alpha_{1}}^{*}[/math], тогда [math]X = {\alpha_{1}}^{*}(\beta + L) = \alpha^{*}(\beta + L)[/math].
[math]\triangleleft[/math]

Решение системы уравнений в регулярных выражениях

Пусть система уравнений имеет вид:


[math] \begin{cases} \alpha_{11} X_1 + \alpha_{12} X_2 + \dots + \alpha_{1n} X_n + \beta_1 = X_1 \\ \alpha_{21} X_1 + \alpha_{22} X_2 + \dots + \alpha_{2n} X_n + \beta_2 = X_2\\ \dots\\ \alpha_{n1} X_1 + \alpha_{n2} X_2 + \dots + \alpha_{nn} X_n + \beta_n = X_n \\ \end{cases} [/math]


Метод решения

Выразим [math]X_1[/math] из первого уравнения и подставим во второе уравнение: [math]X_2 = ( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) X_2 + (\alpha_{21} \alpha_{11}^{*} \alpha_{13} + \alpha_{23}) X_3 + \dots + (\alpha_{21} \alpha_{11}^{*} \alpha_{1n} + \alpha_{2n}) X_n[/math] [math]+ \beta_2[/math].

Пусть [math] a =( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) [/math], [math] b =(\alpha_{21} \alpha_{11}^{*} \alpha_{13} + \alpha_{23}) X_3 + \dots + (\alpha_{21} \alpha_{11}^{*} \alpha_{1n} + \alpha_{2n}) X_n + \beta_2 [/math], тогда уравнение примет вид [math]X_2=a X_2 + b[/math]. Его решением будет [math]a^{*} b[/math]. Подставим в следующее уравнение выраженный [math]X_2[/math].

Далее выполняя схожие итерации получим уравнение [math]X_n = a' X_n + b'[/math], где [math] a'=f( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ),\, b'=g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ) [/math], тогда [math]X_n= f^{*}( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )[/math].

Далее подставляя в полученные в ходе итераций уравнения найденный [math] X_i [/math], обратной прогонкой найдем [math]X_1 \dots X_{n-1} [/math].

Пример решения системы уравнений в регулярных выражениях

Пусть нам нужно найти регулярное выражение, соответствующее языку [math]L_0[/math], слова которого интерпретируются как последовательности чисел [math]0, 1, 2[/math], а языку удовлетворяют слова, сумма чисел в которых делится на 3. Тогда доопределив языки [math]L_1, L_2[/math], сумма чисел в словах из [math]L_i[/math] равна [math]3 - i[/math] по модулю [math]3[/math], получим систему уравнений в регулярных выражениях:

[math] \begin{cases} L_0 = 0L_0 + 1L_1 + 2L_2 + \varepsilon \\ L_1 = 2L_0 + 0L_1 + 1L_2 \\ L_2 = 1L_0 + 2L_1 + 0L_2 \end{cases} [/math]

Поскольку нам нужно найти только [math]L_0[/math], чтобы избежать обратной прогонки, начнём выражать языки с [math]L_2[/math].

[math]L_2 = 0L_2 + (1L_0 + 2L_1), \varepsilon \notin 0 \Rightarrow L_2 = 0^*(1L_0+2L_1)[/math]

[math]L_1 = 2L_0 + 0L_1 + 1L_2 = 2L_0 + 0L_1 + 10^*(1L_0+2L_1) = [/math]

[math] = (0 + 10^*2)L_1 + (2 + 10^*1)L_0, \varepsilon \notin (0 + 10^*2) \Rightarrow L_1 = (0 + 10^*2)^*(2 + 10^*1)L_0[/math]

[math]L_0 = 0L_0 + 1L_1 + 2L_2 + \varepsilon = 0L_0 + 1L_1 + 20^*(1L_0 + 2L_1) + \varepsilon = [/math]

[math] = (0 + 20^*1)L_0 + (1 + 20^*2)L_1 + \varepsilon = [/math]

[math](0 + 20^*1)L_0 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1)L_0 + \varepsilon = [/math]

[math] = (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1))L_0 + \varepsilon [/math]

[math]\varepsilon \notin (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1)) \Rightarrow [/math]

[math] \Rightarrow L_0 = (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1))^* [/math]

Примечания

См. также

Источники информации