CFG와 String 가 주어졌을 때 인지 판정하는 문제를 Membership Problem이라고 한다. CYK Algorithm은 Grammar가 Chomsky Normal Form일 때 Dynamic Programming으로 이 문제를 해결한다.

기본 아이디어

String을 모든 부분 문자열로 나누고, 각 부분 문자열을 생성할 수 있는 Variable의 집합을 Table에 저장한다.

을 위치 에서 시작하는 길이 의 부분 문자열을 생성하는 Variable Set이라고 하자.

최종적으로

이면 String을 Accept한다.

초기화

길이 1인 부분 문자열은 Terminal Production으로 채운다.

점화식

길이 인 부분 문자열을 왼쪽 길이 , 오른쪽 길이 로 나눈다.

이려면 어떤 와 Production 가 있어

를 만족해야 한다.

모든 분할 위치 를 검사한다.

작은 예제

Grammar가

이고 String이 라고 하자.

길이 1 Cell은

이다. , 이고 가 있으므로

이다. 따라서 이다.

Table 방향

구현에서는 2차원 배열을 사용한다. 아래 행에 길이 1인 부분 문자열을 두고 위로 갈수록 긴 부분 문자열을 두는 삼각형 Table로 그리기도 한다. 중요한 것은 위치와 길이를 일관되게 관리하는 것이다.

Parse Tree 복원

Membership만 확인하려면 Variable Set만 저장하면 된다. 실제 Parse Tree를 복원하려면 각 Variable이 어떤 분할 와 Production 를 통해 들어왔는지 Backpointer를 함께 저장한다.

시간복잡도

시작 위치가 , 길이가 , 분할 위치가 이므로 Grammar 크기를 고정하면

이다. Production 탐색 비용까지 포함하면 형태로 표현할 수 있다.

CYK가 CNF를 요구하는 이유

CNF Production 는 부분 문자열을 정확히 두 조각으로 나누는 점화식과 맞는다. Terminal Production 는 길이 1 Cell의 Base Case가 된다.

정리

  • CYK는 CNF Grammar의 Membership을 판정한다.
  • 길이 1 Cell에서 시작하여 더 긴 부분 문자열을 조합한다.
  • Root Cell에 Start Symbol이 있으면 Accept한다.
  • Backpointer를 저장하면 Parse Tree도 복원할 수 있다.

연습 문제

1번

Grammar

에 대해 , 의 Membership을 CYK 관점에서 판정한다.

2번

왜 Production 를 그대로 두면 기본 CYK 점화식에 직접 사용할 수 없는지 설명한다.

풀이

1번

에서는 첫 Cell에 , 둘째 Cell에 가 있고 이므로 Root Cell에 가 들어가 Accept한다. 에서는 둘째 Cell에도 만 있고 가 없으므로 를 만들 수 없어 Reject한다.

2번

기본 CYK는 부분 문자열을 두 조각으로 나누고 를 검사한다. 오른쪽에 Variable이 3개이면 두 조각만으로 직접 대응할 수 없다. CNF 변환으로 , 처럼 Binary Production으로 바꿔야 한다.