CYK Algorithm

상위 문서: Context-Free Languages

개요

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

• $L=L(G)$
• $w=w_1{w}_2\cdots w_n$
• $D(i,l,A)=true\leftrightarrow A\Rightarrow *w_i{w}_{i+1}\cdots w_{i+l-1}$

즉, 위에서 $D(i,l,A)$은 "비단말 $A$가 $w$의 특정 구간을 유도할 수 있는가?"를 기록하는 boolean 테이블이다. 아래는 $D(i,l,A)$가 true가 되는 두가지 경우이다:

1. 문법에 규칙 $A\to a$가 존재하는 경우
   • 입력 문자열의 i번째 문자가 $a$이며 $l=1$
2. 문법에 규칙 $A\to BC$이 존재하는 경우, 어떤 분할점 $k(1\le k<l)$에 아래 두 조건이 모두 참
   • $D(i,k,B)$
   • $D(i+k,l-k,C)$

즉, A가 길이 l의 부분문자열을 만들 수 있으려면 좌측 비단말 B가 앞쪽 부분, 우측 비단말 C가 뒷부분을 생성할 수 있어야 한다. 이때 아래와 같은 명제가 성립한다:

$w\in L\iff (w=ϵ\wedge S\to ϵ)\vee D(1,|w|,S)$

CYK(Cocke–Younger–Kasami) 알고리즘은 위 명제를 바탕으로 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$