클레이니 스타

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

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

정의[편집]

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

이 때 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,
...}

모노이드 구성[편집]

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

같이 보기[편집]