Решение уравнений в регулярных выражениях — различия между версиями
м (rollbackEdits.php mass rollback) |
|||
(не показаны 24 промежуточные версии 4 участников) | |||
Строка 1: | Строка 1: | ||
+ | == Уравнения в регулярных выражениях == | ||
+ | Поскольку алгебра [[Регулярные языки: два определения и их эквивалентность | регулярных выражений]] является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в [[Теория формальных языков | теории формальных языков]], но также была применена к алгоритмам поиска пути в графах<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>. | ||
+ | |||
==Решение уравнений в регулярных выражениях== | ==Решение уравнений в регулярных выражениях== | ||
− | Пусть <tex> | + | Пусть <tex>X</tex> — некий [[Основные_определения:_алфавит,_слово,_язык,_конкатенация,_свободный_моноид_слов;_операции_над_языками | язык]], для которого выполняется равенство <tex>X = \alpha X + \beta </tex>, где <tex>\alpha,\,\beta</tex> — некие регулярные выражения над неким алфавитом <tex>A</tex>. |
{{Утверждение | {{Утверждение | ||
|statement= | |statement= | ||
− | Пусть уравнение имеет вид <tex>X = \alpha X + \beta</tex> | + | Пусть уравнение имеет вид <tex> X = \alpha X + \beta \Rightarrow \, 1)</tex> |
− | если <tex>\varepsilon \notin \alpha | + | если <tex>\varepsilon \notin \alpha </tex>, тогда <tex> \alpha^{*} \beta</tex> — единственное решение <tex>2)</tex> если <tex>\varepsilon \in \alpha </tex>, тогда <tex> \alpha^{*}( \beta + L)</tex> — решение для <tex>\forall L</tex> |
|proof= | |proof= | ||
− | <tex> 1) \varepsilon \notin \alpha </tex>. | + | <tex> 1) </tex> Пусть <tex>\varepsilon \notin \alpha </tex>. Тогда <tex>\forall i \geqslant 0: </tex> выражение <tex>\alpha^{i} \beta \subset X </tex>, следовательно <tex> \alpha^{*} \beta \subset X </tex>. Докажем это индукцией по <tex>i</tex>: при <tex>i = 0</tex> из начального равенства <tex>\beta \subset X</tex>, и если <tex>\alpha^{i} \beta \subset X</tex>, то <tex>\alpha^{i+1} \beta = \alpha \alpha^{i} \beta \subset \alpha X \subset X</tex>. |
+ | Пусть существует <tex> z \in X,\, z\notin \alpha^{*} \beta</tex> такой, что <tex> z </tex> — самое короткое; тогда <tex>z \notin \beta \subset \alpha^{*} \beta \Rightarrow z \in \alpha X, z=z_\alpha z', </tex> где <tex>z_\alpha \in \alpha, z' \in X, z' \notin \alpha^{*} \beta </tex>. | ||
+ | Тогда <tex> z_\alpha \ne \varepsilon \Rightarrow z'</tex> короче <tex>z</tex>, противоречие, тогда не существует самого короткого <tex>z</tex>, значит не существует никакого. | ||
− | |||
− | <tex>\ | + | <tex> 2)</tex> Пусть <tex> \varepsilon \in \alpha</tex>. Тогда можно представить этот язык в виде <tex>\alpha = \varepsilon + \alpha_{1}, \varepsilon \notin \alpha_{1}</tex>, а исходное равенство преобразуется в <tex>\varepsilon X + \alpha_{1} X + \beta = X</tex>. Теперь мы можем взять в качестве базы индукции не просто <tex>\beta</tex>, а любой язык <tex>L \supset \beta</tex>, или, что то же самое, любой <tex>\beta + L</tex>, и дальше показать <tex>\forall i \geqslant 0: {\alpha_{1}}^{i} (\beta + L) \subset X \Rightarrow {\alpha_{1}}^{*} (\beta + L) \subset X</tex>, а потом отсутствие самого короткого <tex>z \in X, z \notin {\alpha_{1}}^{*}(\beta + L)</tex>. Заметим, что <tex>\alpha^{*}={\alpha_{1}}^{*}</tex>, тогда <tex>X = {\alpha_{1}}^{*}(\beta + L) = \alpha^{*}(\beta + L)</tex>. |
}} | }} | ||
==Решение системы уравнений в регулярных выражениях== | ==Решение системы уравнений в регулярных выражениях== | ||
− | Пусть система уравнений имеет вид | + | Пусть система уравнений имеет вид: |
Строка 32: | Строка 36: | ||
− | ''' | + | '''Метод решения''' |
− | + | ||
+ | Выразим <tex>X_1</tex> из первого уравнения и подставим во второе уравнение: <tex>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</tex> <tex>+ \beta_2</tex>. | ||
+ | |||
+ | Пусть <tex> a =( \alpha_{21} \alpha_{11}^{*} \alpha_{12} +\alpha_{22} ) </tex>, <tex> b =(\alpha_{21} \alpha_{11}^{*} \alpha_{13} + \alpha_{23}) X_3 + \dots + (\alpha_{21} \alpha_{11}^{*} \alpha_{1n} + \alpha_{2n}) X_n + \beta_2 </tex>, тогда уравнение примет вид <tex>X_2=a X_2 + b</tex>. Его решением будет <tex>a^{*} b</tex>. Подставим в следующее уравнение выраженный <tex>X_2</tex>. | ||
+ | |||
+ | Далее выполняя схожие итерации получим уравнение <tex>X_n = a' X_n + b'</tex>, где <tex> a'=f( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ),\, b'=g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} ) </tex>, тогда <tex>X_n= f^{*}( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )g( \alpha_{11} \dots \alpha_{1n} \alpha_{2n} \dots \alpha_{nn} )</tex>. | ||
+ | |||
+ | Далее подставляя в полученные в ходе итераций уравнения найденный <tex> X_i </tex>, обратной прогонкой найдем <tex>X_1 \dots X_{n-1} </tex>. | ||
+ | |||
+ | == Пример решения системы уравнений в регулярных выражениях == | ||
+ | Пусть нам нужно найти регулярное выражение, соответствующее языку <tex>L_0</tex>, слова которого интерпретируются как последовательности чисел <tex>0, 1, 2</tex>, а языку удовлетворяют слова, сумма чисел в которых делится на 3. Тогда доопределив языки <tex>L_1, L_2</tex>, сумма чисел в словах из <tex>L_i</tex> равна <tex>3 - i</tex> по модулю <tex>3</tex>, получим систему уравнений в регулярных выражениях: | ||
+ | |||
+ | <tex> | ||
+ | \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} | ||
+ | </tex> | ||
+ | |||
+ | Поскольку нам нужно найти только <tex>L_0</tex>, чтобы избежать обратной прогонки, начнём выражать языки с <tex>L_2</tex>. | ||
+ | |||
+ | <tex>L_2 = 0L_2 + (1L_0 + 2L_1), \varepsilon \notin 0 \Rightarrow L_2 = 0^*(1L_0+2L_1)</tex> | ||
+ | |||
+ | <tex>L_1 = 2L_0 + 0L_1 + 1L_2 = 2L_0 + 0L_1 + 10^*(1L_0+2L_1) = </tex> | ||
+ | |||
+ | <tex> = (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</tex> | ||
+ | |||
+ | <tex>L_0 = 0L_0 + 1L_1 + 2L_2 + \varepsilon = 0L_0 + 1L_1 + 20^*(1L_0 + 2L_1) + \varepsilon = </tex> | ||
+ | |||
+ | <tex> = (0 + 20^*1)L_0 + (1 + 20^*2)L_1 + \varepsilon = </tex> | ||
+ | |||
+ | <tex>(0 + 20^*1)L_0 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1)L_0 + \varepsilon = </tex> | ||
+ | |||
+ | <tex> = (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1))L_0 + \varepsilon </tex> | ||
+ | |||
+ | <tex>\varepsilon \notin (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1)) \Rightarrow </tex> | ||
+ | |||
+ | <tex> \Rightarrow L_0 = (0 + 20^*1 + (1 + 20^*2)(0 + 10^*2)^*(2 + 10^*1))^* </tex> | ||
+ | |||
+ | == Примечания == | ||
+ | <references/> | ||
+ | |||
+ | == См. также == | ||
+ | * [[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]] | ||
+ | |||
+ | == Источники информации == | ||
+ | * [https://ru.wikipedia.org/wiki/Алгебра_Клини Википедия {{---}} Алгебра Клини] | ||
+ | * [https://www.informatik.uni-augsburg.de/lehrstuehle/dbis/pmi/staff/moeller/talks/pdf/dagstuhl.pdf Applications of Kleene Algebra] | ||
+ | * [http://www-sst.informatik.tu-cottbus.de/~wwwti/Studium/04PSAutomaten/Zusamenfassungen/03DuSuikang.pdf Kleene Algebra and Regular Expressions] | ||
+ | |||
+ | [[Категория: Теория формальных языков]] | ||
+ | [[Категория: Автоматы и регулярные языки]] | ||
+ | [[Категория: В разработке]] |
Текущая версия на 19:18, 4 сентября 2022
Уравнения в регулярных выражениях
Поскольку алгебра регулярных выражений является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в теории формальных языков, но также была применена к алгоритмам поиска пути в графах[1], нахождения выпуклой оболочки[2]. В компиляторах она может быть использована для доказательства корректности методик оптимизации циклов[3].
Решение уравнений в регулярных выражениях
Пусть язык, для которого выполняется равенство , где — некие регулярные выражения над неким алфавитом .
— некийУтверждение: |
Пусть уравнение имеет вид
если , тогда — единственное решение если , тогда — решение для |
Пусть . Тогда выражение , следовательно . Докажем это индукцией по : при из начального равенства , и если , то . Пусть существует такой, что — самое короткое; тогда где .Тогда короче , противоречие, тогда не существует самого короткого , значит не существует никакого.
|
Решение системы уравнений в регулярных выражениях
Пусть система уравнений имеет вид:
Метод решения
Выразим
из первого уравнения и подставим во второе уравнение: .Пусть
, , тогда уравнение примет вид . Его решением будет . Подставим в следующее уравнение выраженный .Далее выполняя схожие итерации получим уравнение
, где , тогда .Далее подставляя в полученные в ходе итераций уравнения найденный
, обратной прогонкой найдем .Пример решения системы уравнений в регулярных выражениях
Пусть нам нужно найти регулярное выражение, соответствующее языку
, слова которого интерпретируются как последовательности чисел , а языку удовлетворяют слова, сумма чисел в которых делится на 3. Тогда доопределив языки , сумма чисел в словах из равна по модулю , получим систему уравнений в регулярных выражениях:
Поскольку нам нужно найти только
, чтобы избежать обратной прогонки, начнём выражать языки с .
Примечания
- ↑ R.C. Backhouse, B.A. Carre: Regular algebra applied to path-finding problems. J. Institute of Mathematics and its applications 15, 161-186 (1975)
- ↑ K. Clenaghan: Calculational graph algorithmics: reconciling two approaches with dynamic algebra. CWI Amsterdam, Report CS-R9518, 1995
- ↑ M.C. Patron, D. Kozen: Certification of compiler optimizations using Kleene algebra with tests, Report 99-1779, Computer Science Department, Cornell University, Dec. 1999.