Изменения

Поскольку алгебра [[Регулярные языки: два определения и их эквивалентность | регулярных выражений]] является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в [[Теория формальных языков | теории формальных языков]], но также была применена к алгоритмам поиска пути в графах<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>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>

== Ссылки Примечания ==[https:<references//ru.wikipedia.org/wiki/Алгебра_Клини Википедия {{---}} Алгебра Клини]>

== См. также ==* [https://www.informatik.uni-augsburg.de/lehrstuehle/dbis/pmi/staff/moeller/talks/pdf/dagstuhl.pdf Applications of Kleene Algebra[Альтернативное доказательство теоремы Клини (через систему уравнений в регулярных выражениях)]]

== Источники информации ==* [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]