Изменения

Перейти к: навигация, поиск

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

626 байт добавлено, 23:47, 9 января 2015
Добавлены примечания
== Уравнения в регулярных выражениях ==
Поскольку алгебра [[Регулярные языки: два определения и их эквивалентность | регулярных выражений]] является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в [[Теория формальных языков | теории формальных языков]], но также была применена к алгоритмам поиска пути в графах<ref>R.C. Backhouse, B.A. Carre: ''Regular algebra applied to path-finding problems''. J. Institute of Mathematics and its applicateions '''15''', 161-186 (1975)</ref>, нахождения выпуклой оболочки<ref>K. Clenaghan: ''Calculational graph algorithmics: reconciling two approaches with dynamic algebra''. CWI Amsterdam, Report CS-R9518, 1995</ref>. В компиляторах она может быть использована для доказательства корректности методик оптимизации циклов<ref>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> X_i </tex>, обратной прогонкой найдем <tex>X_1 \dots X_{n-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]
== Источники информации ==* [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]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
[[Категория: В разработке]]
120
правок

Навигация