[계산이론] - (14) CYK 알고리즘 (문맥-자유문법에 대한 소속성 알고리즘)

 

 

 

 

CYK 알고리즘

문법이 Chomsky 정규형인 경우에만 제대로 작동하며, 다음과 같이 문제를 작은 문제로 나누어 해결하는 알고리즘입니다.

Chomsky 정규형민 문법 G = (V, T, S, P)에 대하여, 문자열 w = $a_1...a_n$이 주어졌다고 하겠습니다.


문자열 w의 i번째 심벌부터 j번째 심벌까지의 부문자열을 $w_{ij}$라 하겠습니다. 즉 아래와 같습니다.
$$w_{ij} = a_i...a_j$$

또한 V의 부분집합 $V_{ij}$를 다음과 같이 정의합니다.
$$V_{ij} = \left\{ A \in V \;: \; A \; \overset{*}{\Rightarrow}\; w_{ij}  \right\}$$


이때, 문자열 w는 L(G)에 속하므로,
$$S \in V_{1n}$$


$V_{ij}$를 구하는 데 있어서, A -> $a_i$이고 오직 그럴 때에만 A는 $V_{ij}$에 속합니다.


$V_{ij}$는 다음과 같은 식으로 구해질 수 있습니다.
$$V_{ij} = \cup_{k \in i, (i+1), (i+2), ...} \left\{   A \; : \; A \to BC, \; with \; B \in V_{ik}, \; C \in V_{(k+1)j}  \right\}$$

 

즉 다음과 같은 과정을 통해 소속성 여부를 구할 수 있습니다.

1. $V_{11}$, $V_{22}$, ..., $V_{nn}$을 계산합니다.
2. $V_{12}$, $V_{23}$, ..., $V_{(n-1)n}$을 계산합니다.
3. $V_{13}$, $V_{24}$, ..., $V_{(n-2)n}$을 계산합니다.
...

 

 

 

 

예를 들어 다음과 같습니다.

 

 

 

 

 

 

 

이는 표를 그려 좀 더 보기 편하게 계산할 수 있습니다.

$$V_{11} = \left\{ A\right\}$$	$$V_{22} = \left\{ A\right\}$$	$$V_{33} = \left\{ B\right\}$$	$$V_{44} = \left\{ B\right\}$$	$$V_{55} = \left\{ B\right\}$$
$$V_{12} = \varnothing $$	$$V_{23} = \left\{ S,B \right\}$$	$$V_{34} = \left\{ A\right\}$$	$$V_{45} = \left\{ A\right\}$$
$$V_{13} = \left\{ S,B\right\}$$	$$V_{24} = \left\{ A\right\}$$	$$V_{35} = \left\{ S,B\right\}$$
$$V_{14} = \left\{ A\right\}$$	$$V_{25} = \left\{ S,B\right\}$$
$$V_{15} = \left\{ S,B\right\}$$