クリーネ・スター

形式言語理論 において、クリーネスター（またはクリーネ演算子、クリーネ閉包）とは、記号のアルファベットまたは形式言語（記号の有限列）のいずれにも適用できる、関連する2つの単項演算を指します。

アルファベットV上のクリーネ スター演算子は、V上のすべての有限長文字列の集合V*を生成します^{[注 1 ]。}つまり、要素がVに属する有限シーケンスの集合です。数学では、これは自由モノイド構成としてより一般的に知られています。言語L上のクリーネ スター演算子は、別の言語L*を生成します。これは、 Lの 0 個以上の要素を連結して得られるすべての文字列の集合です。どちらの場合も、繰り返しは許容されます。

クリーネスター演算子は、正規表現のオートマトンを特徴付けるために最初に導入され、広く使用されたアメリカの数学者スティーブン・コール・クリーネにちなんで名付けられました。

アルファベットが与えられた${\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 wv}$1文字を追加して得られる文字列を表します${\displaystyle v}$終わりまで${\displaystyle w}$。 ここ、${\displaystyle V^{i}}$は、長さがちょうどであるすべての文字列の集合と理解できる。${\displaystyle i}$キャラクターは${\displaystyle V}$。

クリーネスターの定義${\displaystyle V}$[ ^{1 ]​}

${\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 L}$（任意の有限または無限の文字列の集合）を定義する

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

${\displaystyle L^{1}=L,}$

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

${\displaystyle L^{i+1}=\{wv:w\in L^{i}{\text{ かつ }}v\in L\}}$各${\displaystyle i>0,}$

どこ${\displaystyle wv}$連結によって得られる文字列を表します${\displaystyle w}$そして${\displaystyle v}$。 ここ、$\displaystyle L^{i}}$は、正確に連結することによって得られるすべての文字列の集合と理解できます。${\displaystyle i}$文字列から${\displaystyle L}$繰り返しを許容する。

クリーネスターの定義${\displaystyle L}$[ ^{2 ]​}

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

形式言語研究（例えばAFL 理論）では、クリーネ スター演算の変形であるクリーネプラスが使用される。クリーネ プラスは、$\displaystyle V^{0}}$または$\displaystyle L^{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.}$^{[注2 ]}

クリーネスターを弦のセットに適用した例：

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

接頭辞プロパティを持たない文字列セットにクリーネスターを適用した例：

{"a","ab","b"} ^* = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...};この例では、文字列 "aab" は 2 通りの方法で取得できます。サルディナス・パターソンアルゴリズムを使用すると、与えられたVに対して、 V ^*のいずれかの要素が複数の方法で取得できるかどうかを確認できます。

文字セットにクリーネとクリーネプラスを適用した例（C言語の慣例に従い、文字はシングルクォーテーション、文字列はダブルクォーテーションで表す）：

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

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

• もし${\displaystyle V}$は任意の有限または可算無限文字の集合である。$\displaystyle V^{*}}$は可算無限集合である。^{[ 1 ]}その結果、有限または可算無限アルファベット上の各形式言語は${\displaystyle \Sigma }$は可算集合である。なぜなら、それは可算無限集合の部分集合だからである。$\displaystyle \Sigma ^{*}}$。
• ${\displaystyle (L^{*})^{*}=L^{*}}$つまり、クリーネスター演算子は冪等単項演算子である。${\displaystyle (L^{*})^{i}=L^{*}}$すべての${\displaystyle i\geq 1}$。
• ${\displaystyle V^{*}=\{\バレプシロン \}}$、 もし${\displaystyle V}$は空集合∅です。言語に対するクリーネスター演算子のバージョンでは、${\displaystyle L^{*}=\{\バレプシロン \}}$いつ${\displaystyle L}$空集合∅または単一要素集合のいずれかである。${\displaystyle \{\varepsilon \}}$。

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

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

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

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