Производные регулярных выражений Януша Бржозовски

Алгоритм МакНотона-Ямады-Томпсона основан на формализме производных Бржозовски.

Производная Бржозовски: \(u^{-1}(L)\) языка \(L\) по строке \(u\); множество всех строк, получаемых из \(L\) удалением префикса \(u\); Формально, над алфавитом \(\Sigma\), \[u^{-1}(L) = \{ v | v \in \Sigma^*, u.v \in L\}.\]

Януш Бржозовски, 1964
алгоритм построения производных регулярных выражений
т.е. построения производной регулярного языка

Во избежание путаницы введём оператор \(\partial_s(r)\)
производная регулярного выражения \(/r/\) по строке \(s\)
\(\partial_u(r)\) – регулярное выражение
может быть вычислено посимвольно относительно строки \(u\) следующим образом:
1. Если \(u = ε\), то \(\partial_u(r) = \partial_ε(r) = r\)
2. Иначе, если \(u = a.v\), то \(\partial_u(r) = \partial_{a.v}(r) = \partial_v (\partial_a(r))\)

Остаётся определить посимвольные производные регулярных выражений

Определим \(\delta(r)\), такую, что если аргумент принимает ε, то она возвращает ε, иначе – \(\varnothing\).

\(\varnothing\) – регулярное выражение, не принимающее никакую входную строку. Конкатенация с \(\varnothing\) с любой стороны очевидно даёт \(\varnothing\).

\(δ(\varnothing) = \varnothing\)
\(δ(ε) = ε\)
\(δ(c) = \varnothing\)
\(δ(r . s) = δ(r) . δ(s)\)
\(δ(r | s) = δ(r) | δ(s)\)
\(δ(r^*) = ε\)

Тогда можем записать:

\(\partial_a(\varnothing) = \varnothing\)
\(\partial_a(ε) = \varnothing\)
\(\partial_a(a) = ε\)
\(\partial_a(b\neq a) = \varnothing\)
\(\partial_a(r . s) = δ(r) . \partial_a(s) | \partial_a(r) . s\)
\(\partial_a(r | s) = \partial_a(r) | \partial_a(s)\)
\(\partial_a(r^*) = \partial_a(r) r^*\)

Если производная \(\partial_u(r)\) принимает пустую строку, то \(/r/\) принимает \(u\).

Owens S., Reppy J., Turon A. Regular-expression derivatives re-examined //Journal of Functional Programming. – 2009. – Т. 19. – №. 2. – С. 173-190.