Производная Бжозовского

В теоретической информатике , в частности в теории формального языка , производная Бжозовского $u^{-1}S$ из набора $S$ из струн и веревки $u$ — это набор всех строк, которые можно получить из строки в $S$ отрезав префикс $u$ . Формально:

u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}

.

Например,

c^{-1}\{{\text{cat}},{\text{cow}},{\text{dog}}\}=\{{\text{at}},{\text{ow}}\}.

Производное Бжозовского было введено под разными названиями с конца 1950-х годов. ^[1]^[2]^[3]Сегодня он назван в честь ученого-компьютерщика Януша Бжозовского , который исследовал его свойства и предложил алгоритм вычисления производной обобщенного регулярного выражения . ^[4]

Определение

Хотя изначально это определение изучалось для регулярных выражений, оно применимо к произвольным формальным языкам.Учитывая любой формальный язык $S$ над алфавитом $\Sigma$ и любая строка $u\in \Sigma ^{*}$ , производная от $S$ относительно $u$ определяется как: ^[5]

u^{-1}S=\{v\in \Sigma ^{*}\mid uv\in S\}

Производная Бжозовского — это частный случай левого фактора по одноэлементному множеству, содержащему только $u$ : $\ u^{-1}S=\{u\}\;\backslash \;S$ .

Эквивалентно для всех $u,v\in \Sigma ^{*}$ :

v\in u^{-1}S\;\Leftrightarrow \;uv\in S.

Из определения для всех $u,v\in \Sigma ^{*}$ :

(uv)^{-1}S=v^{-1}(u^{-1}S)

поскольку для всех $w\in \Sigma ^{*}$ , у нас есть $w\in (uv)^{-1}S\Leftrightarrow uvw\in S\Leftrightarrow vw\in u^{-1}S\Leftrightarrow w\in v^{-1}(u^{-1}S)$ .

Производная по произвольной строке сводится к последовательным производным по символам этой строки, поскольку для всех $a\in \Sigma ,u\in \Sigma ^{*}$ : ${\begin{aligned}(ua)^{-1}S&=a^{-1}(u^{-1}S)\\\varepsilon ^{-1}S&=S\end{aligned}}$

Язык $S\subseteq \Sigma ^{*}$ называется обнуляемым тогда и только тогда, когда он содержит пустую строку $\varepsilon$ . Каждый язык $S$ однозначно определяется обнуляемостью его производных:

w\in S\ \Leftrightarrow \ \varepsilon \in w^{-1}S

Язык можно рассматривать как (потенциально бесконечное) дерево с булевой меткой (см. также дерево (теория множеств) и автомат с бесконечным деревом ). Каждая возможная строка $w\in \Sigma ^{*}$ обозначает узел в дереве с меткой true, когда $w\in S$ и ложь в противном случае. В этой интерпретации производная по символу $a$ соответствует поддереву, полученному путем следования по ребру $a$ от корня. Разложение дерева на корень и поддеревья. $a^{-1}S$ соответствует следующему равенству, справедливому для любого языка $S\subseteq \Sigma ^{*}$ :

S=(\{\varepsilon \}\cap S)\cup \bigcup _{a\in \Sigma }a(a^{-1}S).

Производные обобщенных регулярных выражений

Когда язык задается регулярным выражением, концепция производных приводит к алгоритму определения того, принадлежит ли данное слово регулярному выражению.

Учитывая конечный алфавит A символов, ^[6] обобщенное регулярное выражение R обозначает возможно бесконечное множество строк конечной длины в алфавите A , называемом языком R и обозначаемом L ( R ).

Обобщенным регулярным выражением может быть одно из следующих (где a — символ алфавита A , а R и S — обобщенные регулярные выражения):

«∅» обозначает пустое множество: L (∅) = {},
«ε» обозначает одноэлементный набор, содержащий пустую строку: L (ε) = {ε},
" a " обозначает одноэлементный набор, содержащий односимвольную строку a : L ( a ) = { a },
« R ∨ S » обозначает объединение R и S : L ( R ∨ S ) = L ( R ) ∪ L ( S ),
« R ∧ S » обозначает пересечение R и S : L ( R ∧ S ) = L ( R ) ∩ L ( S ),
«¬ R » обозначает дополнение R (относительно A *, множества всех строк над A ): L (¬ R ) = A * \ L ( R ),
« RS » обозначает объединение R и S : L ( RS ) = L ( R ) · L ( S ),
« R *» обозначает замыкание Клини : R L ( R * ) = L ( R )*.

В обычном регулярном выражении ни ∧, ни ¬ не допускаются.

Вычисление

Для любого данного обобщенного регулярного выражения R и любой строки u производная u ⁻¹R снова является обобщенным регулярным выражением (обозначающим язык u ⁻¹Л ( Р )). ^[7]Его можно вычислить рекурсивно следующим образом. ^[8]

( делать ) ⁻¹Р	= а ⁻¹( в ⁻¹Р )	для символа a и строки u
е ⁻¹Р	= Р

Используя предыдущие два правила, производная по произвольной строке объясняется производной по односимвольной строке a .Последний можно вычислить следующим образом: ^[9]

а ⁻¹а	= е
а ⁻¹б	= ∅	для каждого символа b ≠ a
а ⁻¹е	= ∅
а ⁻¹∅	= ∅
а ⁻¹( Р *)	= ( а ⁻¹Р ) Р *
а ⁻¹( РС )	= ( а ⁻¹р ) S ∨ ν( р ) а ⁻¹С
а ⁻¹( R ∧ S )	= ( а ⁻¹р ) ∧ ( а ⁻¹С )
а ⁻¹( R ∨ S )	= ( а ⁻¹р ) ∨ ( а ⁻¹С )
а ⁻¹(¬ R )	= ¬( а ⁻¹Р )

Здесь $ν(R)$ — вспомогательная функция, дающая обобщенное регулярное выражение, которое возвращает пустую строку ε, если ε язык R содержит , и в противном случае возвращает ∅. Эту функцию можно вычислить по следующим правилам: ^[10]

п( а )	= ∅	для любого символа а
п( е )	= е
п(∅)	= ∅
п( Р *)	= е
ν( РС )	знак равно ν( р ) ∧ ν( S )
ν( р ∧ S )	знак равно ν( р ) ∧ ν( S )
ν( р ∨ S )	знак равно ν( р ) ∨ ν( S )
п(¬ Р )	= е	если ν( R ) = ∅
п(¬ Р )	= ∅	если ν( R ) = е

Характеристики

Строка u является членом набора строк, обозначаемого обобщенным регулярным выражением R, тогда и только тогда, когда ε является членом набора строк, обозначаемого производной u. ⁻¹Р. ^[11]

Учитывая все производные фиксированного обобщенного регулярного выражения, R дает лишь конечное число различных языков. Если их количество обозначить d _R , все эти языки можно получить как производные от R по строкам длины меньше d _R . ^[12] Более того, существует полный детерминированный конечный автомат с d _R состояниями, который распознает регулярный язык, заданный R , как утверждается в теореме Майхилла-Нерода .

Производные контекстно-свободных языков

Производные также эффективно вычислимы для рекурсивно определенных уравнений с операторами регулярных выражений, которые эквивалентны контекстно-свободным грамматикам . Это понимание было использовано для разработки алгоритмов синтаксического анализа для контекстно-свободных языков . ^[13]Было показано, что реализация таких алгоритмов имеет кубическую временную сложность , ^[14]соответствует сложности синтаксического анализатора Эрли для общих контекстно-свободных грамматик.

См. также

Частное формального языка

Ссылки

^ Джордж Н. Рэйни (апрель 1958 г.). «Последовательные функции» . Журнал АКМ . 5 (2): 177–180. дои : 10.1145/320924.320930 . S2CID 1611992 .
^ Дана Скотт и Майкл Рабин (апрель 1959 г.). «Конечные автоматы и проблемы их решения» (PDF) . Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 .
^ Си Си Элгот и Джей Ди Ратледж (октябрь 1961 г.). «Операции над конечными автоматами». В Роберте С. Ледли (ред.). Учеб. AIEE 2-я годовщина. Симп. по коммутации, теории цепей и логическому проектированию (SWCT), Детройт . стр. 129–132. дои : 10.1109/FOCS.1961.26 .
^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .
^ Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .
^ Бжозовский (1964), стр. 481, требовал, чтобы A состояло из 2 ^н комбинации из n битов для некоторого n .
^ Бжозовский (1964), стр.483, Теорема 4.1.
^ Бжозовский (1964), стр.483, Теорема 3.2.
^ Бжозовский (1964), стр.483, Теорема 3.1.
^ Бжозовский (1964), стр.482, Определение 3.2.
^ Бжозовский (1964), стр.483, Теорема 4.2.
^ Бжозовский (1964), стр.484, Теорема 4.3.
^ Мэтью Мэйт; Дэвид Дарайс; Дэниел Спивак (2011). Разбор с производными: функциональный перл . Материалы 16-й международной конференции ACM SIGPLAN по функциональному программированию (ICFP). стр. 189–195. дои : 10.1145/2034773.2034801 .
^ Майкл Д. Адамс; Селеста Холленбек; Мэтью Мэйт (2016). «О сложности и производительности синтаксического анализа с производными». Материалы 37-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . Материалы 37-й конференции ACM SIGPLAN по разработке и реализации языков программирования (PLDI). стр. 224–236. arXiv : 1604.04695 . дои : 10.1145/2908080.2908128 . ISBN 9781450342612 .

[1] Джордж Н. Рэйни (апрель 1958 г.). «Последовательные функции» . Журнал АКМ . 5 (2): 177–180. дои : 10.1145/320924.320930 . S2CID 1611992 .

[2] Дана Скотт и Майкл Рабин (апрель 1959 г.). «Конечные автоматы и проблемы их решения» (PDF) . Журнал исследований и разработок IBM . 3 (2): 114–125. дои : 10.1147/рд.32.0114 .

[3] Си Си Элгот и Джей Ди Ратледж (октябрь 1961 г.). «Операции над конечными автоматами». В Роберте С. Ледли (ред.). Учеб. AIEE 2-я годовщина. Симп. по коммутации, теории цепей и логическому проектированию (SWCT), Детройт . стр. 129–132. дои : 10.1109/FOCS.1961.26 .

[4] Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .

[5] Януш А. Бжозовский (1964). «Производные регулярных выражений» . Дж АСМ . 11 (4): 481–494. дои : 10.1145/321239.321249 . S2CID 14126942 .

[6] Бжозовский (1964), стр. 481, требовал, чтобы A состояло из 2 ^н комбинации из n битов для некоторого n .

[7] Бжозовский (1964), стр.483, Теорема 4.1.

[8] Бжозовский (1964), стр.483, Теорема 3.2.

[9] Бжозовский (1964), стр.483, Теорема 3.1.

[10] Бжозовский (1964), стр.482, Определение 3.2.

[11] Бжозовский (1964), стр.483, Теорема 4.2.

[12] Бжозовский (1964), стр.484, Теорема 4.3.

[13] Мэтью Мэйт; Дэвид Дарайс; Дэниел Спивак (2011). Разбор с производными: функциональный перл . Материалы 16-й международной конференции ACM SIGPLAN по функциональному программированию (ICFP). стр. 189–195. дои : 10.1145/2034773.2034801 .

[14] Майкл Д. Адамс; Селеста Холленбек; Мэтью Мэйт (2016). «О сложности и производительности синтаксического анализа с производными». Материалы 37-й конференции ACM SIGPLAN по проектированию и реализации языков программирования . Материалы 37-й конференции ACM SIGPLAN по разработке и реализации языков программирования (PLDI). стр. 224–236. arXiv : 1604.04695 . дои : 10.1145/2908080.2908128 . ISBN 9781450342612 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]