클린 별
Kleene star수리 논리학과 컴퓨터 과학에서, 클린 별(또는 클린 연산자 또는 클린 닫힘)은 문자열 집합이나 기호 또는 문자 집합에서 단항 연산자이다.수학에서는 자유모노이드 구조라고 더 일반적으로 알려져 있다.V {\ V에 대한 클린별의 적용은 V {\ V로 표기되어 있으며, 이는 Stephen Kleene이 "0회 이상의 반복"을 의미하는 특정 오토마타를 특징짓기 위해 도입한 문맥이다.
- V{\ V가 문자열 세트인 V{\V은 (는) 빈 인{\ \을 포함하는 {\ V의 최소 슈퍼셋으로 정의되며 문자열 연결 조작으로 닫힙니다.
- V{\ V가 기호 또는 문자 집합인 V{\ V는 V{\V의 기호 위에 있는 모든 문자열 집합입니다( 문자열
V { { V { * }can 、 빈 문자열과 모든 유한 길이의 문자열을 포함하는 세트라고도 할 수 있습니다이 세트는 V의 임의의 요소를 하여 동일한 요소를 여러 번 사용할 수 있습니다.만약 V{V\displaystyle}중 하나는 빈 세트 ∅거나 singleton{ε}{\displaystyle\와 같이{\varepsilon)}을 세웠다}, V∗){ε}{\displaystyle V^{*}=\{\varepsilon)}};만약 V{V\displaystyle}은 다른 플레이어와 한정되어 있거나 셀 수 있게 무한 집합을, V({\displaystyle V^{*}}은 셀 수 있게 무한 집합을 설정한다.[1]따라서 유한 또는 계산 가능한 무한 알파벳(\ 상의 각 공식 언어는 계산 가능한 무한 집합 의 서브셋이기 때문에 계산 가능합니다.
정의 및 표기법
된 V V 정의
- 0 { V^ { 0 } \ { \ \} (빈 문자열로만 구성된 언어),
이 세트를 재귀적으로 정의하다
- > 0 \ i \ i > 1 { w \ { : w \ V^ { } { \ text { }\ V\ } 。
V V가 공식 언어인 , V(\ V의i)의 인 Vdisplaystyle V)는 V(\V를그 로 연결하는 입니다, V i{\ V는 V{\ V에서i {\ i 의 결합으로 표현될 수 있는 모든 문자열의 집합으로 이해할 수 있습니다.
브이에서[2] 클린 스타의 정의는
즉, Kleene 별 연산자는 문자열 또는 문자의 V {\V에 대해( )V {\displaystyle (V^{*})^{*} = = V∗ {{displaystyle V = V ∗{{*} }}입니다
클린 플러스
일부 공식 언어 연구(예: AFL 이론)에서는 클린 플러스라고 불리는 클린 별 연산에 대한 변형이 사용됩니다.Kleene 플러스에서는 위의 조합에서 0 V 가 생략됩니다. 클린 플러스는
또는
예
문자열 집합에 적용되는 Kleene 별 예:
- {"ab""c"}* = { 、 "ab", "c", "abab", "cab", "cab", "abab", "abc", "abc", "abc", "abc", "cabc", "cabc", "cabc", "cabc", "cabc"...".
문자 집합에 적용되는 Kleen plus의 예:
- {"a", "b", "c"}+ = { "a", "b", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cb", "cb", "cb", "cb", "c", "cb", "c", "c", "c", "c", "c", "a", "cb", "a", "a", "c", "a", "a", "c", "aab", "c", "aab", "c", "c", "c", "c", "c
동일한 문자 집합에 적용되는 Kleene 별:
- {"a", "b", "c"}* = { ε, "a", "b", "a", "ab", "ac", "bb", "bb", "bc", "ca", "cb", "cb", "c", "cb", "c", "c", "cb", "c", "c", "c", "c", "c", "a", "a", "a", "a", "a", "a", "a", "a", "aab", "aab", "aab", "c", "c", "..."......"
빈 집합에 적용된 Kleene 별의 예:
- ∅ = {filename}입니다.*
빈 세트에 적용되는 Kleen plus의 예:
- = +*= = = { } = 、
여기서 concatenation은 연관성과 비교환성을 나타내는 곱입니다.
빈 문자열이 포함된 싱글톤 세트에 적용되는 Kleene plus 및 Kleene star의 예:
- { V \ { \ \ 이면 각 { i}에 i { { V^ { i } \ { \ \ }= + = { } { V { } { } { }
일반화
문자열은 연결을 바이너리 연산으로 하고 ID 요소를 사용하여 모노이드를 형성합니다.클라인별은 문자열뿐만 아니라 모든 모노이드에 대해 정의됩니다.보다 정확하게는 (M, ))을 모노이드로 하고, S m M으로 한다.다음으로* S는 S를 포함한 M의 가장 작은 서브모노이드이다. 즉, S는* M의 중성 원소인 집합 S를 포함하며, x,y s* S이면 xyy s* S가 된다.
또한 클렌별은 완전한 별 [4]반선의 개념에 의해 대수 구조 자체에 *-연산(및 결합)을 포함시킴으로써 일반화된다.
「 」를 참조해 주세요.
레퍼런스
- ^ Nayuki Minase (10 May 2011). "Countable sets and Kleene star". Project Nayuki. Retrieved 11 January 2012.
- ^ Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics. Brooks/Cole. p. 656. ISBN 0534923739.
The Kleene closure L* of L is defined to be .
- ^ 이 방정식은 V의+ 모든 원소가 V의 한 원소로 구성되어야 하며 V에서 비어 있지 않은 항이 완전히 많거나 V의 한 원소에 불과하기 때문에 성립한다(여기서 V는 θ와 연결된 V를 취함으로써 검색된다).
- ^ Droste, M.; Kuich, W. (2009). "Chapter 1: Semirings and Formal Power Series". Handbook of Weighted Automata. Monographs in Theoretical Computer Science. Springer. p. 9. doi:10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.