Обнуляемость (регулярные выражения)

В «Производных регулярных выражений» Бжозовского и в других местах функция δ (R), возвращающая λ, если R допускает значение NULL, и ∅ в противном случае, включает следующие пункты:

δ(R1 + R2) = δ(R1) + δ(R2)
δ(R1 · R2) = δ(R1) ∧ δ(R2)

Ясно, что если и R1, и R2 допускают значение NULL, то (R1 · R2) допускает значение NULL, и если либо R1 или R2 допускает значение NULL, тогда (R1 + R2) допускает значение NULL. Однако мне неясно, что означают приведенные выше пункты. Моя первая мысль, отображающая (+), (·) или булевы операции на регулярные множества, бессмысленна, поскольку в базовом случае

δ(a) = ∅ (for all a ∈ Σ)
δ(λ) = λ
δ(∅) = ∅

и λ не является набором (и набор не является возвращаемым типом δ, который является регулярным выражением). Кроме того, это отображение не указывается, и для него есть отдельное обозначение. Я понимаю обнуляемость, но я потерялся в определении суммы, произведения и логических операций в определении δ: как λ или ∅ возвращаются из δ(R1) ∧ δ(R2), например, в определении off δ(R1 · R2)?


nullable regex derivative
person danportin    schedule 02.01.2011    source источник
comment
Вместо этого это должно быть на Theoretical CS: cstheory.stackexchange.com   -  person Wolph    schedule 02.01.2011
comment
У меня сложилось впечатление, что cstheory.stackexchange предназначен для вопросов исследовательского уровня. Если да, то этот вопрос, безусловно, не подходит для сайта. На этом сайте много вопросов такого уровня по регулярным выражениям.   -  person danportin    schedule 02.01.2011
comment
Меня устраивает почти все на SO, но этот вопрос меня бесконечно смущает. Я думаю, вы получите больше внимания на cstheory.   -  person bukzor    schedule 07.01.2011

Ответы (3)


arrow_upward
2
arrow_downward

Я думаю, что вы попадаете в ловушку условных свобод, принятых автором. Тип возвращаемого значения δ(R) наверняка является набором или, скорее, языком. Если вы посмотрите на определение:

альтернативный текст

вы можете видеть, что есть несоответствие в возвращаемом типе, формально λ является элементом, но ∅ является пустым языком... Что он должен сказать:

альтернативный текст

Тот факт, что автор использует λ как для пустой строки, так и для языка, содержащего только пустую строку, подтверждается его определением оператора звезды Клини:

альтернативный текст

Очевидно, что последняя часть должна быть alt text, если мы хотим быть педантичными.

Учитывая, что возвращаемый тип δ(R) является набором или, скорее, языком, уравнения, которые вы даете, имеют смысл и точно выражают то, что вы описали.

person wich    schedule 11.01.2011
comment
Я считаю, что вы правы. Я привык видеть L(R) (или любое эквивалентное обозначение, например [R]) для языка регулярных выражений. Остается странным, что автор использует δ в определении производных для обозначения регулярного выражения. Если δ обозначает регулярное выражение, а не язык ({λ} или ∅), любое из регулярных выражений λ или ∅ получается в рекурсивных случаях δ с помощью простой алгебры (например, ∅ + λ = λ). - person danportin; 11.01.2011

arrow_upward
3
arrow_downward

Я думаю, вы были правы, сопоставив + и ^ с логическими or и and соответственно. Похоже, две приведенные вами строки имеют дело с альтернациями (сумма) и конкатенацией (продукт):

δ(R1 + R2) = δ(R1) + δ(R2)

чередование R1 и R2 допускает значение NULL, если R1 допускает значение NULL, R2 допускает значение NULL или оба R1 и R2 допускают значение NULL.

δ(R1 · R2) = δ(R1) ∧ δ(R2)

Конкатенация R1 и R2 допускает значение NULL только в том случае, если и R1, и R2 допускают значение NULL.

См. здесь реализацию этих правил в Haskell.

person Frédéric Hamidi    schedule 02.01.2011
comment
Хм. Если бы я определял функцию nullable, подходящими предложениями были бы nullable(R1 + R2) = nullable(R1) ∨ nullable(R2) (как вы сказали, сумма R1 и R2 допускает значение NULL, если дизъюнкция значений nullable(R1) и nullable(R2) истинна) и nullable(R1 · R2) = nullable(R1) ∧ nullable(R2). Таким образом, я мог четко определить функцию δ как δ(R) = case nullable(R) of True -> λ; Ложь -› ∅. Хотя это правильно, я думаю, что это не главное, поскольку возвращаемое значение функции равно λ или пустому языку, и в ней не используется механизм, подобный case. - person danportin; 02.01.2011

arrow_upward
2
arrow_downward

(не могу заглянуть в статью Бжозовского, чтобы лучше понять, что там имеется в виду), но могу предложить 2 способа трактовки этой записи (кроме того, чтобы согласиться с записью, я вижу, вопросов нет: смысл этого определения хорошо понятен):

1) Слева от определения у нас есть только «синтаксические» шаблоны для регулярных выражений. Справа производим наборы; помните, что регулярное выражение — это способ обозначить язык (множество), поэтому такой способ записи определения становится понятным: справа мы просто используем некоторые (простые) регулярные выражения как краткий способ обращения к наборы. То есть ∅ означает пустой язык (пустое множество), а λ (если интерпретировать как регулярное выражение) означает язык, содержащий только пустое слово (множество с этим элементом).

Операции — это просто операции над множествами: вероятно, объединение и пересечение.

Если нотация интерпретируется таким образом, нет противоречия с используемой нотацией, чтобы игнорировать базовый случай: опять же, «а» - это регулярное выражение, которое означает язык со словом «а».

2) Мы строим регулярные выражения сначала справа, но автор расширил операции построения регулярных выражений клином, который имеет семантику пересечения языков.

person imz -- Ivan Zakharyaschev    schedule 10.01.2011