クリーネ閉包

クリーネ閉包（くりーねへいほう、英: Kleene closure）は、形式言語とオートマトンの理論において、ある演算の繰り返しが「生成」するシンボルないし文字の列（文字列）の集合である。また、この繰り返しの単項演算子をクリーネスター（英: Kleene star）という。

集合 V に対するクリーネ閉包の適用は、V* と表す。スティーヴン・コール・クリーネがある種のオートマトンを特徴付けるために導入した方法である、正規表現でよく用いられる。

  1. V が文字列の集合であるとき、V* は、空文字列 ε を含み、文字列連結演算に閉じているような最小の集合と定義される。この集合は、別の書き方をすれば、V に含まれるゼロ個以上の文字列を連結して作ることができるような文字列の集合である。
  2. V がシンボル・文字の集合であるとき、V* は、空文字列を含む V 上のあらゆる文字列の集合である。

例

文字列の集合に適用されるクリーネ閉包の例：

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

文字の集合に適用されるクリーネ閉包の例：

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

一般化

クリーネ閉包はしばしば、以下のようなモノイド (M, .) 、つまり以下の条件を満たす集合 M と M 上の二項演算「.」として一般化される。

  • （閉包）あらゆる a、b ∈ M に対し、a . b ∈ M
  • （結合法則）あらゆる a、b 、c ∈ M に対し、(a . b) . c = a . (b . c)
  • （単位元）ある ε ∈ M が存在して、あらゆる a ∈ M で a . ε = ε . a = a

V が M の部分集合であるとき、V* は ε（空文字列）を含み、演算に閉じているような最小の集合である。このとき V* それ自身もモノイドになり、「V によって生成されたモノイド」という。シンボルの集合上の（二項演算としての文字列連結による）あらゆる文字列の集合はモノイドを成すから、これはクリーネ閉包の一般化である。

関連項目