concatenation - 集合論における連結の表記法

Question

オートマトン理論クラスの宿題に取り組んでいます。これまでのところ、正規表現を含む単なる証明であり、それほどクレイジーではありません。とにかく、私の質問は、これは連結のための適切なセット表記法は何ですか? たとえば、R + S が R union S と同じであることはわかっていますが、私の人生では、連結に相当する集合論が何であるかを思い出せません。

私は問題に取り組んでいると思うので、問題を投稿するつもりはありません.誰かが私に正しい方向に少し突っ込んでもらえますか?

Answer 1

通常のセットの連結について言及していると思います。通常、連結またはドット演算子は、通常のセットの連結を示します。同じ表記が正規表現にも適用されます。例えば

• AB = A·B = { xy : x ∈ A & y ∈ B }

正式には、正則集合はクリーネ代数を形成します。これは、一連の公理を満たすクリーネ スター演算子をもつ冪等半環です。冪等半環のような代数では、乗算は通常、連結またはドット演算子を介して表現されます。これが、正規集合の連結 (クリーネ代数における乗算演算) が連結またはドット演算子で示される理由です。正規表現も同様です。

Answer 2

文字列はセットではないため、R + S は R union S と同じではありません。文字列はセットであるアルファベット上にあります。(ただし、技術的には、文字列を一連の順序付けられたペア (char、index) として表すこともできます)。

連結するときは、R + S とだけ言う必要があります。一般セットを連結することはできません。

ただし、一連の文字列を連結することはできます。文字列 U と V のセット (連結) の場合、UV は uv の形式のすべての文字列で構成されます。ここで、u は U からの文字列で、v は V からの文字列です。これはクロス積に少し似ています。