クリーネスター

数理論理学とコンピュータサイエンス において、クリーネスター（またはクリーネ演算子、クリーネ閉包）は、文字列の集合または記号や文字の集合に対する単項演算である。数学では、自由モノイド構成としてよく知られている。クリーネスターの集合への適用は、と表記される。これは、スティーブン・クリーネが特定のオートマトンを特徴付けるために導入した文脈であり、正規表現で広く使用されており、その文脈では「0回以上の繰り返し」を意味する。 ${\displaystyle V}$${\displaystyle V^{*}}$

1. が文字列の集合である場合、 は空の文字列を含み、文字列連結演算で閉じられているの最小のスーパーセットとして定義されます。${\displaystyle V}$${\displaystyle V^{*}}$${\displaystyle V}$ ${\displaystyle \epsilon }$
2. が記号または文字の集合である場合、 は空の文字列 を含む、内の記号上のすべての文字列の集合です。${\displaystyle V}$${\displaystyle V^{*}}$${\displaystyle V}$${\displaystyle \epsilon }$

集合は、空文字列と、 の任意の要素を連結して生成できる有限長の文字列すべてを含む集合としても記述でき、同じ要素を複数回使用できます。 が空集合∅ または単集合 のいずれかである場合、 です。が他の有限集合または可算無限集合である場合、 は可算無限集合です。^[1]結果として、有限または可算無限アルファベット上の各形式言語は可算です。これは、可算無限集合 のサブセットであるためです。 ${\displaystyle V^{*}}$${\displaystyle V}$${\displaystyle V}$${\displaystyle \{\varepsilon \}}$${\displaystyle V^{*}=\{\バレプシロン \}}$${\displaystyle V}$${\displaystyle V^{*}}$${\displaystyle \Sigma }$${\displaystyle \Sigma^{*}}$

演算子は生成文法の書き換え規則で使用されます。

集合 が与えられたとき、定義する ${\displaystyle V}$

${\displaystyle V^{0}=\{\バレプシロン \}}$（空の文字列のみで構成される言語）、

${\displaystyle V^{1}=V}$、

そして集合を再帰的に定義する

${\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ および }}v\in V\}}$それぞれについて。${\displaystyle i>0}$

が形式言語である場合、集合 の - 乗である は、集合 をそれ自身と で連結したものの省略形です。つまり、 は、内の文字列の連結として表すことができるすべての文字列の集合であると理解できます。 ${\displaystyle V}$${\displaystyle V^{i}}$${\displaystyle i}$${\displaystyle V}$${\displaystyle V}$${\displaystyle i}$${\displaystyle V^{i}}$${\displaystyle i}$${\displaystyle V}$

クリーネ星の定義は^[2]である。${\displaystyle V}$

${\displaystyle V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3} \cup V^{4}\cup \cdots .}$

これは、クリーネ スター演算子が、任意の 文字列または文字のセットに対して、すべての と同様に、べき等単項演算子であることを意味します。 ${\displaystyle (V^{*})^{*}=V^{*}}$${\displaystyle V}$${\displaystyle (V^{*})^{i}=V^{*}}$${\displaystyle i\geq 1}$

いくつかの形式言語研究（例えばAFL理論）では、クリーネスター演算のバリエーションであるクリーネプラスが使用される。クリーネプラスは上記の和集合の項を省略する。言い換えれば、クリーネプラスは ${\displaystyle V^{0}}$${\displaystyle V}$

${\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots ,}$

または

${\displaystyle V^{+}=V^{*}V.}$^[3]

文字列のセットに適用された Kleene スターの例:

{"ab","c"} ^* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc"、"cabab"、"cabc"、"ccab"、"ccc"、...}。

文字セットに Kleene plus を適用した例:

{"a", "b", "c"} ⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab"、...}。

同じ文字セットに Kleene スターを適用した場合:

{"a", "b", "c"} ^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc"、"ca"、"cb"、"cc"、"aaa"、"aab"、...}。

空集合に適用されたクリーネスターの例:

∅ ^* = {ε}です。

空集合に適用されたクリーネ加算の例:

∅ ⁺ = ∅ ∅ ^* = { } = ∅、

ここで、連結は結合的かつ非可換的な積です。

空の文字列を含むシングルトン セットに適用された Kleene plus と Kleene star の例:

ならば、各 についても となるので、したがって となります。${\displaystyle V=\{\varepsilon \}}$${\displaystyle V^{i}=\{\バレプシロン \}}$${\displaystyle i}$${\displaystyle V^{*}=V^{+}=\{\バレプシロン \}}$

文字列は、連結を二項演算とし、 ε を単位元とするモノイドを形成します。クリーネ星は、文字列だけでなく、任意のモノイドに対して定義されます。より正確には、 ( M , ⋅) をモノイドとし、S ⊆ Mとします。このとき、 S ^{* は}Sを含むMの最小のサブモノイドです。つまり、S ^{* は}Mの中立元である集合Sを含み、x , y ∈ S ^*ならばx ⋅ y ∈ S ^*となるようなものになります。

さらに、クリーネスターは、完全なスター半環の概念によって代数構造自体に*演算（および和集合）を含めることによって一般化されます。^[4]

• ワイルドカード文字
• Glob（プログラミング）

• ホップクロフト、ジョン E. ;ウルマン、ジェフリー D. (1979)。オートマトン理論、言語、計算入門(第 1 版)。Addison -Wesley。