클레이니 스타 (Kleene Star)는 문자열 이나 문자 의 집합 에 쓰이는 단항 연산 으로, 0개 이상의 임의 원소의 연쇄 를 뜻한다. 스티븐 클레이니 가 도입하였으며, 오토마타 이론 과 정규 표현식 , 형식 문법 에서 활용된다. 일반적으로 수학에서는 자유 모노이드 구성에 쓰인다. Σ* 는 시그마의 클레이너 스타, 또는 간단히 시그마 스타라고 읽는다.
집합 V의 임의 n회 연쇄를 다음과 같이 정의한다.
V
0
=
{
ε
}
{\displaystyle V^{0}=\{\varepsilon \}}
V
1
=
V
{\displaystyle V^{1}=V}
V
n
=
V
∘
V
n
−
1
=
{
u
v
|
u
∈
V
,
v
∈
V
n
−
1
}
(
n
≥
2
)
{\displaystyle V^{n}=V\circ V^{n-1}=\{uv|u\in V,v\in V^{n-1}\}(n\geq 2)}
이 때 V의 클레이니 스타는 다음과 같이 정의한다.
V
∗
=
⋃
⋃
i
=
0
∞
V
i
=
⋃
i
∈
N
V
i
=
{
ε
}
∪
V
∪
V
2
∪
V
3
∪
V
4
∪
…
.
{\displaystyle V^{*}=\sideset {}{_{i=0}^{\infty }}\bigcup V^{i}=\bigcup _{i\in \mathbb {N} }V^{i}=\{\varepsilon \}\cup V\cup V^{2}\cup V^{3}\cup V^{4}\cup \ldots .}
클레이니 플러스는 다음과 같이 정의된다.빈 문자열을 포함하지 않는 클레이니 스타이다.
V
+
=
⋃
⋃
i
=
1
∞
V
i
=
V
∪
V
2
∪
V
3
∪
V
4
∪
…
.
=
V
V
∗
{\displaystyle V^{+}=\sideset {}{_{i=1}^{\infty }}\bigcup V^{i}=V\cup V^{2}\cup V^{3}\cup V^{4}\cup \ldots .=VV^{*}}
여기서
V
{\displaystyle V}
V
+
=
V
∗
−
{
ε
}
{\displaystyle V^{+}=V^{*}-\{\varepsilon \}}
V
{\displaystyle V}
V
+
=
V
∗
{\displaystyle V^{+}=V^{*}}
ε,
a, b,
aa, ab, ba, bb,
aaa, aab, aba, abb, baa, bab, bba, bbb, ...} ε,
ab, c,
abab, abc, cab, cc,
ababab, ababc, abcab, abcc, cabab, cabc, ccab, ccc, ...}
∅
∗
=
{
ε
}
{\displaystyle \varnothing ^{*}=\{\varepsilon \}}
∅
+
=
∅
∅
∗
=
{
}
=
∅
{\displaystyle \varnothing ^{+}=\varnothing \varnothing ^{*}=\{\}=\varnothing }
(
M
,
⋅
)
{\displaystyle (M,\cdot )}
(
N
∗
,
⋅
)
{\displaystyle (N^{*},\cdot )}
