클레이니 스타
이 문서의 내용은 출처가 분명하지 않습니다. (2013년 2월) |
클레이니 스타(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을 포함하는 최소의 모노이드는 이다.