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