Решение уравнений в регулярных выражениях — различия между версиями
Genyaz (обсуждение | вклад) м (Добавлены ссылки) |
м (rollbackEdits.php mass rollback) |
||
(не показаны 2 промежуточные версии 2 участников) | |||
Строка 47: | Строка 47: | ||
== Пример решения системы уравнений в регулярных выражениях == | == Пример решения системы уравнений в регулярных выражениях == | ||
− | Пусть нам | + | Пусть нам нужно найти регулярное выражение, соответствующее языку <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> | <tex> |
Текущая версия на 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.