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$와 같은 규칙 대신, 해당 변수들이 만들어낼 수 있는 규칙으로 대체해야 한다. 따라서 이를 일괄적으로 적용하면 아래와 같은 결과가 된다:

$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$
$S_0\to A{S}_1|SA|AS|A_{2}B|a$
$A\to A{A}_1|SA|AS|A_{2}B|a|b$ 
$B\to b$
$S_1\to SA$
$A_1\to SA$
$A_2\to a$