클레이니 스타

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

클레이니 스타는 형식 언어 이론에서 문자열 집합에 적용되는 단항 연산이다. 집합 V의 클레이니 스타는 V에 있는 문자열을 0번 이상 연결하여 만들 수 있는 모든 문자열의 집합이며, V*로 표기한다. 클레이니 스타는 멱등원 단항 연산자이며, 클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타를 의미한다. 클레이니 스타는 모노이드에서도 정의되며, 문자열 연결 외에도 다양한 분야에서 응용된다.

클레이니 스타

📚 더 읽어볼만한 페이지

형식 언어 - 문자열
문자열은 사람이 읽을 수 있는 텍스트를 저장하고 정보를 전달하거나 받는 데 사용되는 순서가 있는 문자들의 시퀀스로, 다양한 형태의 데이터를 표현하며 유한한 길이를 가지고, 프로그래밍 언어에서 기본 또는 복합 자료형으로 제공되고, 문자 집합과 인코딩 방식에 따라 표현 방식이 달라진다.
형식 언어 - 튜링 기계
튜링 기계는 앨런 튜링이 제시한 계산 모델로, 테이프 위에서 기계적으로 작동하며, 유한한 상태, 테이프, 헤드, 명령 표를 통해 작동하고, 계산 가능성과 알고리즘의 한계를 연구하는 데 사용된다.
자연어 처리 - 정보 추출
정보 추출은 비정형 또는 반구조화된 텍스트에서 구조화된 정보를 자동으로 추출하는 기술로, 자연어 처리 기술을 활용하여 개체명 인식, 관계 추출 등의 작업을 수행하며 웹의 방대한 데이터에서 유용한 정보를 얻는 데 사용된다.
자연어 처리 - 단어 의미 중의성 해소
단어 의미 중의성 해소(WSD)는 문맥 내 단어의 의미를 파악하는 계산 언어학 과제로, 다양한 접근 방식과 외부 지식 소스를 활용하여 연구되고 있으며, 다국어 및 교차 언어 WSD 등으로 발전하며 국제 경연 대회를 통해 평가된다.
문법 - 접속사
접속사는 문장, 절, 구, 단어와 같은 언어 요소들을 연결하여 논리적 관계를 나타내는 품사로, 등위 접속사, 종속 접속사, 상관 접속사 등으로 나뉘며, 언어에 따라 다양한 형태로 나타난다.
문법 - 품사
품사는 형태, 기능, 의미에 따라 단어를 분류하는 언어학적 범주로, 언어별 특징과 문법화 과정에 따라 분류 체계와 구성원이 달라지며, 품사 간 경계가 모호한 경우도 있어 여러 언어에서 다양한 논의가 이루어지고 있다.

1. 개요
2. 정의
- 2.1. 클레이니 플러스
3. 예시
4. 일반화
5. 성질

2. 정의

집합 V에 대하여, 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의 i 거듭제곱은 V를 자기 자신과 i번 연결하는 것을 의미하며, V에 있는 i개의 문자열을 연결하여 만들 수 있는 모든 문자열의 집합이다. 클레이니 스타는 V에 속한 문자열들을 0개 이상 연결하여 만들 수 있는 모든 문자열의 집합을 나타내며, 멱등원 단항 연산자이다. 즉, $(V^{*})^{*}=V^{*}$ 이며, 모든 $i\geq 1$ 에 대해 $(V^{*})^{i}=V^{*}$ 이다.

2.1. 클레이니 플러스

클레이니 플러스는 빈 문자열을 포함하지 않는 클레이니 스타이다.

: $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^*$

일부 형식 언어 연구 (예: AFL 이론)에서는 클레이니 스타 연산의 변형인 "클레이니 플러스"가 사용된다. 클레이니 플러스는 위의 합집합에서 $V^{0}$ 항을 생략한다. 즉, $V$ 에 대한 클레이니 플러스는 다음과 같다.

: $V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,$

또는

: $V^+ = V^*V.$

3. 예시

클레이니 스타가 문자열 집합에 적용된 예는 다음과 같다.

:{ "ab", "c" }^* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

클레이니 플러스가 문자 집합에 적용된 예는 다음과 같다.

:{ "a", "b", "c" }⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

클레이니 스타가 동일한 문자 집합에 적용된 예는 다음과 같다.

:{ "a", "b", "c" }^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

클레이니 스타가 빈 집합에 적용된 예는 다음과 같다.

:∅^* = {ε}.

클레이니 플러스가 빈 집합에 적용된 예는 다음과 같다.

:∅⁺ = ∅ ∅^* = { } = ∅.

여기서 연결은 결합 법칙과 비교환 법칙을 따른다.

클레이니 플러스와 클레이니 스타가 빈 문자열을 포함하는 단일 집합에 적용된 예는 다음과 같다.

: 만약 $V=\{\varepsilon\}$ 이면, 각 $i$ 에 대해 $V^{i}=\{\varepsilon\}$ 이므로 $V^{*}=V^{+}=\{\varepsilon\}$ 이다.

4. 일반화

$(M, \cdot)$ 이 모노이드이고, V가 M의 부분 집합일 때, V^*는 ε (빈 문자열)을 포함하고 연산에 닫혀 있는 최소의 집합이다. V^* 자체도 모노이드가 되며, "V에 의해 생성된 모노이드"라고 한다. 기호 집합 위의 (이항 연산으로서의 문자열 연결에 의한) 모든 문자열의 집합은 모노이드를 이루므로, 이것은 클레이니 스타의 일반화이다.

클레이니 스타는 다음 조건을 만족하는 집합 M과 M 위의 이항 연산 " . "을 갖는 모노이드 (M, .)로 일반화되기도 한다.

* (폐쇄성) 모든 a, b ∈ M에 대해, a . b ∈ M
* (결합 법칙) 모든 a, b, c ∈ M에 대해, (a . b) . c = a . (b . c)
* (항등원) 어떤 ε ∈ M이 존재하여, 모든 a ∈ M에 대해 a . ε = ε . a = a

클레이니 스타는 완전 스타 반환의 개념을 통해 *-연산(및 합집합)을 대수 구조 자체에 포함시켜 일반화된다.

5. 성질

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

집합 $V$ 가 주어졌을 때, 다음과 같이 정의한다.

: $V^{0}=\{\varepsilon\}$ (빈 문자열만으로 구성된 언어)
: $V^{1}=V$

그리고 각 $i>0$ 에 대해 집합을 재귀적으로 정의한다.

: $V^{i+1}=\{wv: w\in V^{i} \text{ and } v\in V \}$

$V$ 가 형식 언어인 경우, 집합 $V$ 의 $i$ 거듭제곱인 $V^i$ 는 집합 $V$ 를 자기 자신과 $i$ 번 연결하는 것을 줄여서 표현한 것이다. 즉, $V^i$ 는 $V$ 에 있는 $i$ 개의 문자열을 연결하여 나타낼 수 있는 모든 문자열의 집합으로 이해할 수 있다.

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

: $V^*=\bigcup_{i \ge 0 }V^i = V^0 \cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots.$

이것은 클레이니 스타 연산자가 임의의 문자열 또는 문자 집합 $V$ 에 대해 멱등원 단항 연산자임을 의미한다. 즉, $(V^{*})^{*}=V^{*}$ 이며, 모든 $i\geq 1$ 에 대해 $(V^{*})^{i}=V^{*}$ 이다.

일부 형식 언어 연구 (예: AFL 이론)에서는 클레이니 스타 연산의 변형인 "클레이니 플러스"가 사용된다. 클레이니 플러스는 위의 합집합에서 $V^{0}$ 항을 생략한다. 즉, $V$ 에 대한 클레이니 플러스는 다음과 같다.

: $V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,$

또는

: $V^+ = V^*V.$

문자열은 이항 연산으로 연결, 항등원으로 ε를 갖는 모노이드를 형성한다. 클레이니 스타는 문자열뿐만 아니라 모든 모노이드에 대해 정의된다.

더 정확히 말하면, (M, ⋅)를 모노이드, S ⊆ M이라고 하자. 그러면 S^*는 S를 포함하는 가장 작은 M의 부분 모노이드이다. 즉, S^*는 M의 항등원, 집합 S를 포함하며, x,y ∈ S^*일 경우 x⋅y ∈ S^*를 만족한다.

또한, 클레이니 스타는 완전 스타 반환의 개념을 통해 *-연산(및 합집합)을 대수 구조 자체에 포함시켜 일반화된다.