클레이니 스타

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

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

정의[편집]

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

V^0 = \{\varepsilon\}
V^1 = V
V^n = V \circ V^{n-1} = \{uv|u\in V, v\in V^{n-1}\} (n \ge 2)

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

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.

클레이니 플러스[편집]

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

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

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

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

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

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,
...}
  • \varnothing ^* =\{\varepsilon\}.
  • \varnothing ^+ = \varnothing \varnothing ^* =\{\}= \varnothing,

모노이드 구성[편집]

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

같이 보기[편집]