CYK Algorithm - 편집 역사

2025년 10월 26일 (일) 04:34에 Pinkgo님의 편집

2025-10-26T04:34:16Z

← 이전 판		2025년 10월 26일 (일) 04:34 판
4번째 줄:		4번째 줄:

	==개요==		==개요==

	CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 <math>L</math>에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 <math>w</math>를 입력받아, 그 문자열이 언어 <math>L</math>에 속하는지 여부를 판별하는 알고리즘이다. 이때 아래와 같이 수식이 정의된다:		CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 <math>L</math>에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 <math>w</math>를 입력받아, 그 문자열이 언어 <math>L</math>에 속하는지 여부를 판별하는 알고리즘이다. 이때 아래와 같이 수식이 정의된다:
	* <math>L = L(G)</math><ref>즉, <math>L</math>이 생성하는 언어를 의미한다.</ref>		* <math>L = L(G)</math><ref>즉, <math>L</math>이 생성하는 언어를 의미한다.</ref>

Pinkgo: /* Time Complexity of the CYK Algorithm */

2025-10-26T02:31:41Z

Time Complexity of the CYK Algorithm

← 이전 판		2025년 10월 26일 (일) 02:31 판
36번째 줄:		36번째 줄:

	==Time Complexity of the CYK Algorithm==		==Time Complexity of the CYK Algorithm==
	CYK 알고리즘의 시간 복잡도는 <math>O^3\cdot \|G\|</math>이다. 이때 n은 입력 문자열의 길이이고, \|G\|는 문법의 규칙 수이다. 이는 다른 일반적인 CFL 판별 알고리즘(Earley 등)과 비슷한 수준이다.		CYK 알고리즘의 시간 복잡도는 <math>O(n^3\cdot \|G\|)</math>이다. 이때 n은 입력 문자열의 길이이고, \|G\|는 문법의 규칙 수이다. 이는 다른 일반적인 CFL 판별 알고리즘(Earley 등)과 비슷한 수준이다.

	==각주==		==각주==

2025년 10월 26일 (일) 02:30에 Pinkgo님의 편집

2025-10-26T02:30:51Z

← 이전 판		2025년 10월 26일 (일) 02:30 판
19번째 줄:		19번째 줄:
	CYK(Cocke–Younger–Kasami) 알고리즘은 위 명제를 바탕으로 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.		CYK(Cocke–Younger–Kasami) 알고리즘은 위 명제를 바탕으로 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.

	<math></math>		==Implementation of CYK Algorithm==
	<math></math>		===Initialization Step===
	<math></math>		CYK 알고리즘을 수행하기 위해서는 먼저 모든 D(i,l,A)를 false로 초기화해야 한다. 또한 각 w의 각 문자 위치 <math>i = 1sim n</math>에 대해 문법의 모든 규칙 <math>A \rightarrow a</math>를 확인하여 만약 <math>w_i = a</math>이면 <math>D(i,1,A)=true</math>로 설정한다.
	<math></math>
	<math></math>		===Main Loop===
	<math></math>		CYK 알고리즘의 main loop에서는 문자열 길이 2 이상인 구간을 처리한다. 아래는 이를 수행하는 코드이다:
	<math></math>		<syntaxhighlight lang="c#">
	<math></math>		for l from 2 to n: // 부분문자열의 길이
	<math></math>		for i from 1 to n - (l - 1): // 시작 위치
	<math></math>		for k from 1 to l - 1: // 분할 위치
			for each rule A → BC:
			if D(i, k, B) and D(i+k, l-k, C) are true:
			set D(i, l, A) = true
			</syntaxhighlight>
			즉, 모든 가능한 부분 문자열 구간과 그 분할점을 고려하면서 어떤 비단말 A가 그 구간을 생성할 수 있는지를 동적 프로그래밍으로 확인하는 것이다. 이를 실행한 뒤, <math>D(1,n,S)=true</math>이면 입력 문자열 <math>w</math>는 시작 단말 <math>S</math>로부터 유도 가능한 것이다. 즉, 이 경우 주어진 <math>w</math>는 <math>w \in L</math>을 만족한다.

			==Time Complexity of the CYK Algorithm==
			CYK 알고리즘의 시간 복잡도는 <math>O^3\cdot \|G\|</math>이다. 이때 n은 입력 문자열의 길이이고, \|G\|는 문법의 규칙 수이다. 이는 다른 일반적인 CFL 판별 알고리즘(Earley 등)과 비슷한 수준이다.

	==각주==		==각주==

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 $L$ 에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 $w$ 를 입력받아, 그 문자열이 언어 $L$ 에 속하는...

2025-10-26T02:09:40Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 <math>L</math>에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 <math>w</math>를 입력받아, 그 문자열이 언어 <math>L</math>에 속하는...

새 문서

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Grammars#Context-Free Languages#CYK Algorithm|Context-Free Languages]]

==개요==

CNF으로 변환된 문법을 기반으로, 주어진 문자열이 언어 <math>L</math>에 속하는지를 결정론적으로(deterministic) 판단할 수 있다. 이때 recognizer라는 개념이 등장하는데, recognizer는 문자열 <math>w</math>를 입력받아, 그 문자열이 언어 <math>L</math>에 속하는지 여부를 판별하는 알고리즘이다. 이때 아래와 같이 수식이 정의된다:
* <math>L = L(G)</math><ref>즉, <math>L</math>이 생성하는 언어를 의미한다.</ref>
* <math>w = w_1w_2\cdots w_n</math>
* <math>D(i, l, A) = true \leftrightarrow A \Rightarrow* w_iw_{i+1}\cdots w_{i+l-1}</math><ref>이는 비단말 <math>A</math>가 <math>w</math>의 i번째 문자부터 길이 <math>l</math>만큼의 부분 문자열을 생성할 수 있으면 true라는 의미이다.</ref>
즉, 위에서 <math>D(i, l, A)</math>은 "비단말 <math>A</math>가 <math>w</math>의 특정 구간을 유도할 수 있는가?"를 기록하는 boolean 테이블이다. 아래는 <math>D(i, l, A)</math>가 true가 되는 두가지 경우이다:
# 문법에 규칙 <math>A \rightarrow a</math>가 존재하는 경우
#* 입력 문자열의 i번째 문자가 <math>a</math>이며 <math>l = 1</math>
# 문법에 규칙 <math>A \rightarrow BC</math>이 존재하는 경우, 어떤 분할점 <math>k\,\, (1 \le k < l)</math>에 아래 두 조건이 모두 참
#* <math>D(i,k,B)</math>
#* <math>D(i+k, l-k, C)</math>
즉, A가 길이 l의 부분문자열을 만들 수 있으려면 좌측 비단말 B가 앞쪽 부분, 우측 비단말 C가 뒷부분을 생성할 수 있어야 한다. 이때 아래와 같은 명제가 성립한다:
<math>w \in L \Leftrightarrow (w = \epsilon \land S \rightarrow \epsilon) \lor D(1, |w|, S)</math>
CYK(Cocke–Younger–Kasami) 알고리즘은 위 명제를 바탕으로 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.

<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>
<math></math>

==각주==