클레이니 스타

클레이니 스타(Kleene Star)는 문자열이나 문자의 집합에 쓰이는 단항 연산으로, 0개 이상의 임의 원소의 연쇄를 뜻한다. 스티븐 클레이니가 도입하였으며, 오토마타 이론과 정규 표현식, 형식 문법에서 활용된다. 일반적으로 수학에서는 자유 모노이드 구성에 쓰인다. Σ*는 시그마의 클레이너 스타, 또는 간단히 시그마 스타라고 읽는다.

정의

집합 V의 임의 n회 연쇄를 다음과 같이 정의한다.

${\displaystyle V^{0}=\{\varepsilon \}}$

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

${\displaystyle V^{n}=V\circ V^{n-1}=\{uv|u\in V,v\in V^{n-1}\}(n\geq 2)}$

이 때 V의 클레이니 스타는 다음과 같이 정의한다.

${\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 .}$

클레이니 플러스

클레이니 플러스는 다음과 같이 정의된다.빈 문자열을 포함하지 않는 클레이니 스타이다.

${\displaystyle V^{+}=\sideset {}{_{i=1}^{\infty }}\bigcup V^{i}=V\cup V^{2}\cup V^{3}\cup V^{4}\cup \ldots .=VV^{*}}$

여기서 ${\displaystyle V}$가 빈 문자열을 포함하지 않는다면 클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타와 같다.

${\displaystyle V^{+}=V^{*}-\{\varepsilon \}}$

${\displaystyle V}$가 빈 문자열을 포함한다면 클레이니 플러스는 클레이니 스타와 같다.

${\displaystyle V^{+}=V^{*}}$

예시

• {a, b}* = {

ε,

a, b,

aa, ab, ba, bb,

aaa, aab, aba, abb, baa, bab, bba, bbb,

...}

• {ab, c}* = {

ε,

ab, c,

abab, abc, cab, cc,

ababab, ababc, abcab, abcc, cabab, cabc, ccab, ccc,

...}

• ${\displaystyle \varnothing ^{*}=\{\varepsilon \}}$
• ${\displaystyle \varnothing ^{+}=\varnothing \varnothing ^{*}=\{\}=\varnothing }$

모노이드 구성

${\displaystyle (M,\cdot )}$이 모노이드라 가정하자. 연쇄 연산은 결합법칙을 만족하므로, 즉 ε∈M이고 M은 연쇄 연산에 닫혀 있다. 이 때 M의 부분집합 N에 대해 N을 포함하는 최소의 모노이드는 ${\displaystyle (N^{*},\cdot )}$이다.

같이 보기

• 정규 언어
• 정규 표현식