120
правок
Изменения
Добавлено введение об алгебре Клини
== Уравнения в регулярных выражениях ==
Поскольку алгебра [[Регулярные языки: два определения и их эквивалентность | регулярных выражений]] является частным случаем алгебры Клини, то и соответствующие уравнения можно рассматривать как уравнения алгебры Клини. Сама эта алгебра классически используется в [[Теория формальных языков | теории формальных языков]], но также была применена к алгоритмам поиска пути в графах, нахождения выпуклой оболочки. В компиляторах она может быть использована для доказательства корректности методик оптимизации циклов.
==Решение уравнений в регулярных выражениях==
Пусть <tex>X</tex> — некий [[Основные_определения:_алфавит,_слово,_язык,_конкатенация,_свободный_моноид_слов;_операции_над_языками | язык]], для которого выполняется равенство <tex>X = \alpha X + \beta </tex>, где <tex>\alpha,\,\beta</tex> — некие [[Регулярные_языки:_два_определения_и_их_эквивалентность | регулярные выражения]] над неким алфавитом <tex>A</tex>.
{{Утверждение
== Ссылки ==
[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]
[[Категория: Теория формальных языков]]
[[Категория: Автоматы и регулярные языки]]
