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

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

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

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

Производные регулярных выражений можно обозначать так же, как производные языков, но мы во избежание путаницы введём оператор \(\partial_s(r)\), который будет означать производную регулярного выражения \(/r/\) по строке \(s\).

Для произвольного регулярного выражения \(r\), и произвольной строки \(u\), производная \(\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\):

\[\begin{align} δ(\varnothing) & = \varnothing \\ δ(ε) & = ε \\ δ(c) & = \varnothing \\ δ(r . s) & = δ(r) . δ(s) \\ δ(r | s) & = δ(r) | δ(s) \\ δ(r^*) & = ε \\ \end{align}\]

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

Тогда для посимвольных производных относительно символа \(a\) можем записать:

\[\begin{align} \partial_a(\varnothing) & = \varnothing \\ \partial_a(ε) & = \varnothing \\ \partial_a(a) & = ε \\ \partial_a(b) & = \varnothing & (a \neq b) \\ \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^* \\ \end{align}\]

Используя эти определения, оказывается легко проверить, принимает ли регулярное выражение \(r\) произвольную строку \(u\): для этого достаточно вычислить производную \(\partial_u(r)\). Если производная принимает пустую строку, то \(r\) принимает \(u\).