Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Производная Бжозовского (на красном фоне) словарной строки, заданной по " con "

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

Определение [ править ]

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

u −1 S = { v ∈ Σ * : uv ∈ S }

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

v ∈ u −1 S тогда и только тогда, когда uv ∈ S

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

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

v ∈ (uw) −1 S тогда и только тогда, когда uwv ∈ S тогда и только тогда, когда wv ∈ u −1 S тогда и только тогда, когда v ∈ w −1 ( u −1 S )

так что (uw) −1 S = w −1 ( u −1 S ).

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

( ua ) −1 S= a −1 ( u −1 S )     
ε −1 S= S

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

w ∈ S тогда и только тогда, когда ε ∈ w −1 S

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

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

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

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

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

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

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

Вычисление [ править ]

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

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

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

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

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

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

Свойства [ править ]

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

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

Производные от контекстно-свободных языков [ править ]

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

См. Также [ править ]

Ссылки [ править ]

  1. ↑ Джордж Н. Рэйни (апрель 1958 г.). «Последовательные функции» . Журнал ACM . 5 (2): 177–180.
  2. ↑ Дана Скотт и Майкл Рабин (апрель 1959). «Конечные автоматы и проблемы их решения» (PDF) . Журнал исследований и разработок IBM . 3 (2): 114–125.
  3. ^ CC Элгот и JD Рутледж (октябрь 1961). «Операции над конечными автоматами». В Роберте С. Ледли (ред.). Proc. AIEE 2nd Ann. Symp. по коммутации, теории цепей и логическому проектированию (SWCT), Детройт . С. 129–132. DOI : 10.1109 / FOCS.1961.26 .
  4. ↑ Януш А. Бжозовский (1964). «Производные от регулярных выражений». J ACM . 11 (4): 481–494. DOI : 10.1145 / 321239.321249 .
  5. ↑ Януш А. Бжозовский (1964). «Производные от регулярных выражений». J ACM . 11 (4): 481–494. DOI : 10.1145 / 321239.321249 .
  6. ^ Бжозовского (1964), p.481, требуется A состоит из 2 -х п комбинаций п битов , для некоторого п .
  7. ^ Brzozowski (1964), p.483, теорема 4.1
  8. ^ Brzozowski (1964), p.483, теорема 3.2
  9. ^ Бжозовского (1964), p.483, теорема 3.1
  10. ^ Brzozowski (1964), p.482, определение 3.2
  11. ^ Brzozowski (1964), p.483, теорема 4.2
  12. ^ Brzozowski (1964), p.484, теорема 4.3
  13. ↑ Мэтью Майт; Дэвид Дарэ; Даниэль Спивак (2011). Разбор производными: функциональная жемчужина . Материалы 16-й международной конференции ACM SIGPLAN по функциональному программированию (ICFP). С. 189–195. DOI : 10.1145 / 2034773.2034801 .
  14. ^ Майкл Д. Адамс; Селеста Холленбек; Мэтью Майт (2016). О сложности и производительности парсинга с производными . Труды 37-й конференции ACM SIGPLAN по проектированию и реализации языков программирования (PLDI). С. 224–236. DOI : 10.1145 / 2908080.2908128 .