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

Производная Бжозовского (на красном фоне) словарной строки, установленной относительно "против"

В теоретическая информатика, в частности в формальная теория языка, то Производная Бжозовского ты−1S из набор S струн и нить ты определяется как набор всех строк, получаемых из строки в S отрезав префикс ты, формально: ты−1S = { v ∈ Σ*: УФ ∈ S }, ср. Он был представлен под разными названиями с конца 1950-х годов.[1][2][3]Сегодня он назван в честь компьютерного ученого. Януш Бжозовски которые исследовали их свойства и дали алгоритм для вычисления производной обобщенного регулярное выражение.[4]

Определение

Несмотря на то, что изначально изучались регулярные выражения, определение применимо к произвольным формальным языкам. формальный язык S над алфавитом Σ и любая строка ты ∈ Σ*, производная от S относительно ты определяется как:[5]

ты−1S = { v ∈ Σ*: УФ ∈ S }

Эквивалентный способ заявить об этом для всех ты,v ∈ Σ*:

v ∈ ты−1S если только УФ ∈ S

что дает некоторую интуицию для обозначений.

Из определения для всех ты,v,ш ∈ Σ*:

v ∈ (ух)−1S если только uwv ∈ S если только wv ∈ ты−1S если только v ∈ ш−1(ты−1S)

так (ух)−1S = ш−1(ты−1S).

Производная по произвольной строке сводится к последовательным производным по символам этой строки, потому что для а∈ Σ, ты∈ Σ*:

(ua)−1S= а−1(ты−1S)     
ε−1S= S

Язык L⊆ Σ* называется обнуляемый если он содержит пустую строку, то есть ε ∈ L. Каждый язык S однозначно определяется допуском к нулю его производных:

ш ∈ S если только ε ∈ ш−1S

Язык можно рассматривать как (потенциально бесконечное) логическое обозначение дерево (смотрите также дерево (теория множеств) и автомат с бесконечным деревом ). Каждая возможная строка ш ∈ Σ* обозначает позицию в дереве с двоичной меткой истинный когда ш ∈ S и ложный когда ш ∉ S. В этой интерпретации производная по символу а соответствует вычислению поддерева, полученного следом за ребром а. Разбиение дерева на корень и поддеревья а−1S соответствует следующему равенству, которое выполняется для любого формального языка S⊆ Σ*:

S = ({ε} ∩S) ∪ ⋃а∈Σ а(а−1S).

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

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

Учитывая конечное алфавит А символов,[6] а обобщенное регулярное выражение обозначает возможно бесконечное множество строк символов конечной длины из А. Он может быть построен из:

  • ∅ (обозначает пустой набор строк),
  • ε (обозначает одноэлементный набор, содержащий только пустую строку),
  • символ а из А (обозначает одноэлементный набор, содержащий строку с одним символом а),
  • р∨S (куда р и S являются, в свою очередь, обобщенными регулярными выражениями; обозначая их объединение множества),
  • р∧S (обозначает пересечение р 'песок S набор),
  • ¬р (обозначающий дополнение р установлен относительно набора всех строк символов из А),
  • RS (обозначающий набор всех возможных конкатенаций строк из р 'песок S набор),
  • р* (обозначая набор п-кратные повторы струн из р набор, для любого п≥0, включая пустую строку).

В обычном регулярном выражении нельзя использовать ни ∧, ни ¬. Набор строк, обозначаемый обобщенным регулярным выражением р называется его язык, обозначенный как L(р).

Вычисление

Для любого данного обобщенного регулярного выражения р и любая строка ты, производная ты−1р снова является обобщенным регулярным выражением.[7]Его можно вычислить рекурсивно следующим образом.[8]

(ua)−1р= а−1(ты−1р) для символа а и строка ты
ε−1р= р

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

а−1а= ε
а−1б= ∅для каждого символа б≠а
а−1ε= ∅
а−1∅= ∅
а−1(р*)= (а−1R) R*
а−1(RS)= (а−1р)S ∨ ν (р)а−1S
а−1(р∧S)= (а−1р) ∧ (а−1S)
а−1(р∨S)= (а−1р) ∨ (а−1S)
а−1(¬р)= ¬(а−1р)

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

ν (а)= ∅для любого символа а
ν (ε)= ε
ν (∅)= ∅
ν (р*)= ε
ν (RS)= ν (р) ∧ ν (S)
ν (р ∧ S)= ν (р) ∧ ν (S)
ν (р ∨ S)= ν (р) ∨ ν (S)
ν (¬р)= εесли ν (р) = ∅
ν (¬р)= ∅если ν (р) = ε

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

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

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

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

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

Смотрите также

Рекомендации

  1. ^ Джордж Н. Рэйни (апрель 1958 г.). «Последовательные функции». Журнал ACM. 5 (2): 177–180.
  2. ^ Дана Скотт и Майкл Рабин (апрель 1959 г.). «Конечные автоматы и проблемы их решения» (PDF). Журнал исследований и разработок IBM. 3 (2): 114–125.
  3. ^ C.C. Элгот и Дж.Д. Ратледж (октябрь 1961 г.). «Операции над конечными автоматами». В Роберте С. Ледли (ред.). Proc. AIEE 2nd Ann. Symp. по коммутации, теории схем и логическому проектированию (SWCT), Детройт. С. 129–132. Дои:10.1109 / FOCS.1961.26.
  4. ^ Януш А. Бжозовский (1964). «Производные от регулярных выражений». J ACM. 11 (4): 481–494. Дои:10.1145/321239.321249.
  5. ^ Януш А. Бжозовский (1964). «Производные от регулярных выражений». J ACM. 11 (4): 481–494. Дои:10.1145/321239.321249.
  6. ^ Бжозовский (1964), с.481, требуется А состоять из 2п комбинации п биты, для некоторых п.
  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 по проектированию и реализации языков программирования (PLDI). С. 224–236. Дои:10.1145/2908080.2908128.