클레이니 스타 문서 원본 보기

{{위키데이터 속성 추적}}
{{출처 필요|날짜=2013-2-8}}
'''클레이니 스타'''(Kleene Star)는 [[문자열]]이나 [[문자]]의 [[집합]]에 쓰이는 [[단항 연산]]으로, 0개 이상의 임의 원소의 [[연쇄]]를 뜻한다. [[스티븐 클레이니]]가 도입하였으며, [[오토마타 이론]]과 [[정규 표현식]], [[형식 문법]]에서 활용된다. 일반적으로 수학에서는 자유 [[모노이드]] 구성에 쓰인다. '''Σ*'''는 시그마의 클레이너 스타, 또는 간단히 시그마 스타라고 읽는다.

== 정의 ==
집합 V의 임의 n회 연쇄를 다음과 같이 정의한다.
:<math>V^0 = \{\varepsilon\}</math>
:<math>V^1 = V</math>
:<math>V^n = V \circ V^{n-1} = \{uv|u\in V, v\in V^{n-1}\} (n \ge 2)</math>
이 때 V의 클레이니 스타는 다음과 같이 정의한다.
:<math>V^* = \sideset{}{_{i=0}^\infty}\bigcup V^i = \bigcup_{i \in \N }V^i = \{\varepsilon\} \cup V \cup V^2 \cup V^3 \cup V^4 \cup \ldots.</math>

=== 클레이니 플러스 ===
클레이니 플러스는 다음과 같이 정의된다.빈 문자열을 포함하지 않는 클레이니 스타이다.
:<math>V^+ = \sideset{}{_{i=1}^\infty}\bigcup V^i = V \cup V^2 \cup V^3 \cup V^4 \cup \ldots. = VV^*</math>
여기서 <math>V</math>가 빈 문자열을 포함하지 않는다면 클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타와 같다.
:<math>V^+ = V^* - \{\varepsilon\}</math>
<math>V</math>가 빈 문자열을 포함한다면 클레이니 플러스는 클레이니 스타와 같다.
:<math>V^+ = V^*</math>

== 예시 ==
* {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,
:...}
* <math>\varnothing ^* =\{\varepsilon\}</math>
* <math>\varnothing ^+ = \varnothing \varnothing ^* =\{\}= \varnothing </math>

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

== 같이 보기 ==
* [[정규 언어]]
* [[정규 표현식]]

{{집합론}}
{{계산 이론}}

[[분류:형식 언어]]
[[분류:문법]]
[[분류:자연어 처리]]