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

Question

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

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

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

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

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

Answer 1

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

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

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

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

сцепление * * * * * * * * * * * * * * * *

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *1030* * *1030* * * * * * * * * * *1030* * * * * * * * * *1030* * * * * * * * * *1030* * * * * * * * * * * *1030* * * * * * * * *1030* * * * * * * *1030* * * * * *1030*

Answer 2

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

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

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

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

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

Answer 3

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

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

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

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

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