Chomsky Normal Form

상위 문서: Context-Free Languages

개요

CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법(Grammars)으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다:

1. $A\to BC$
2. $A\to a$
3. $S\to ϵ$

CFG를 CNF로 바꾸더라도 새로운 문자열이 생성되지는 않으며, 모든 grammar와 문자열이 그대로 보존된다.

CFG to CNF

아래와 같이 CFG가 주어졌다고 가정하자:

$S\to ASA|aB$
$A\to B|S$
$B\to b|ϵ$

Step 1

CNF에서는 시작기호가 우변에 등장하면 안 되므로, 기존 시작기호 $S$를 포함하는 새 시작기호 $S_0$를 만든다. 이를 통해 모든 변환은 $S_0$에서 시작한다. 이를 통해 아래와 같은 식을 추가한다:

$S_0\to S$

Step 2

주어진 식에 $B\to ϵ$이 존재하므로 제거해야 한다. 이를 위해서 $B\to ϵ$ 규칙을 제거하고, $B$를 포함하는 식이 유도되는 모든 규칙에서, $B$를 $ϵ$으로 치환한 아래의 식을 추가한다:

$S\to aB\to a$
$A\to B\to ϵ$

위와 같은 과정을 $A\to ϵ$ 규칙에 대해서도 동일하게 적용해야 한다. 이를 위해 해당 식을 제거하고, 아래의 식들을 추가한다:

$S\to S$
$S\to AS$
$S\to SA$

또한, $A\to S,A\to B,S\to$와 같은 규칙 대신, 해당 변수들이 만들어낼 수 있는 규칙으로 대체해야 한다. 따라서 이를 일괄적으로 적용하면 아래와 같은 결과가 된다:

$S\to ASA|SA|AS|aB|a$
$B\to b$
$S_0\to ASA|SA|AS|aB|a$ 
$A\to ASA|SA|AS|aB|a$ 
$A\to b$ 

Step 3

이제, CNF에서는 규칙의 오른쪽에 두개의 비단말만 가능하므로 3개 변수인 $ASA$ 형태를 분해해야 한다. 이를 위해 해당 규칙을 아래와 같이 중간 비단말 $S_1,A_1$을 활용한 규칙들로 대체해야 한다.:

$S\to A{S}_1$
$S_1\to SA$
$A\to A{A}_1$
$A_1\to SA$

또한, CNF에서는 단말이 반드시 단독으로만 나와야 하므로, $S\to aB$와 같은 규칙은 허용되지 않는다. 따라서 해당 규칙을 아래와 같이 중간 비단말 $A_2$을 활용한 규칙들로 대체해야 한다:

$A_2\to a$
$S\to A_{2}B$

따라서 아래와 같이 최종적인 CNF가 도출된다:

$S\to A{S}_1|SA|AS|A_{2}B|a$
$B\to b$
$S_0\to A{S}_1|SA|AS|A_{2}B|a$
$A\to A{A}_1|SA|AS|A_{2}B|a$ 
$A\to b$ 
$A_2\to a$

CYK Algorithm

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 }$