regex - Nullability (正規表現)

Question

Brzozowski の「Derivatives of Regular Expressions」などでは、R が null 許容の場合は λ を返し、それ以外の場合は ∅ を返す関数 δ(R) には、次のような句が含まれています。

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

明らかに、R1とR2の両方が null 許容の場合、( R1 · R2 ) は null 許容であり、R1またはR2のいずれかが null 許容の場合、( R1 + R2 ) は null 許容です。ただし、上記の条項が何を意味するのかは不明です。私の最初の考えでは、(+)、(·)、またはブール演算を通常のセットにマッピングすることは無意味です。

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

λ はセットではありません (セットは正規表現である δ の戻り値の型でもありません)。さらに、このマッピングは示されておらず、別の表記法があります。Null 可能性は理解していますが、δ の定義における和、積、およびブール演算の定義についてはわかりません。たとえば、定義でδ( R1 ) ∧ δ( R2 ) から λ または ∅ が返される方法を教えてください。 off δ( R1・R2 )?

Answer 1

私はあなたがマップ+し^、ブール値orとandそれぞれに正しかったと思います。あなたが引用した2行は、交互（合計）と連結（積）を扱っているようです：

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

が null 可能であるか、null 可能であるか、またはその両方であり、かつnull 可能である場合、andの代替はnull 可能です。R1R2R1R2R1R2

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

andの連結は、との両方が null 許容である場合にのみ null許容です。R1R2R1R2

これらのルールの Haskell 実装については、こちらを参照してください。

Answer 2

(Brzozowski の記事を調べて、そこにある意味をよりよく理解することはできません)、しかし、この表記法を解釈する 2 つの方法を提案できます (表記法とうまくやっていくことは別として、わかりました、疑問の余地はありません: 意図されたこの定義の意味はよく理解されています):

1) 定義の左側には、正規表現の「構文」パターンがあります。右側では、セットを生成します。正規表現は言語 (セット) を表す方法であることを覚えておいてください。したがって、定義を書き留めるこの方法は理解できるようになります。セットします。つまり、∅ は空の言語 (空のセット) を意味し、λ (正規表現として解釈される場合) は空の単語 (この要素を持つセット) のみを含む言語を意味します。

操作は単にセットに対する操作です。おそらく和集合と交差です。

表記がこのように解釈される場合、基本ケースを無視するために使用される表記と矛盾はありません。繰り返しますが、「a」は、単語「a」を含む言語を意味する正規表現です。

2) そもそも正規表現を構築するのは右側ですが、著者は正規表現を構築する操作を、言語の交差のセマンティクスを持つウェッジで拡張しました。

Answer 3

著者が取った自由な表記法にあなたは巻き込まれていると思います。δ(R) の戻り値の型は、間違いなくセット、またはむしろ言語です。定義を見ると：

戻り値の型に矛盾があることがわかります。正式には λ は要素ですが、∅ は空の言語です... 言うべきことは次のとおりです。

著者が空の文字列と空の文字列のみを含む言語の両方に λ を使用するという事実は、Kleene スター演算子の彼の定義によってさらに証明されます。

明らかに、最後の部分は、衒学的になりたい場合です。

δ(R) の戻り値の型がセット、またはむしろ言語であることを考えると、あなたが与える方程式は完全に理にかなっていて、あなたが説明したことを正確に表現しています。