Chomsky Normal Form

상위 문서: Context-Free Languages

개요

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

1. [math]\displaystyle{ A \rightarrow BC }[/math]
2. [math]\displaystyle{ A \rightarrow a }[/math]
3. [math]\displaystyle{ S \rightarrow \epsilon }[/math]

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

CFG to CNF

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

[math]\displaystyle{ S \rightarrow ASA | aB }[/math]
[math]\displaystyle{ A \rightarrow B | S }[/math]
[math]\displaystyle{ B \rightarrow b | \epsilon }[/math]

Step 1

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

[math]\displaystyle{ S_0 \rightarrow S }[/math]

Step 2

주어진 식에 [math]\displaystyle{ B \rightarrow \epsilon }[/math]이 존재하므로 제거해야 한다. 이를 위해서 [math]\displaystyle{ B\rightarrow \epsilon }[/math] 규칙을 제거하고, [math]\displaystyle{ B }[/math]를 포함하는 식이 유도되는 모든 규칙에서, [math]\displaystyle{ B }[/math]를 [math]\displaystyle{ \epsilon }[/math]으로 치환한 아래의 식을 추가한다:

[math]\displaystyle{ S \rightarrow aB \rightarrow a }[/math]
[math]\displaystyle{ A \rightarrow B \rightarrow \epsilon }[/math]

위와 같은 과정을 [math]\displaystyle{ A \rightarrow \epsilon }[/math] 규칙에 대해서도 동일하게 적용해야 한다. 이를 위해 해당 식을 제거하고, 아래의 식들을 추가한다:

[math]\displaystyle{ S \rightarrow S }[/math]
[math]\displaystyle{ S \rightarrow AS }[/math]
[math]\displaystyle{ S \rightarrow SA }[/math]

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

[math]\displaystyle{ S \rightarrow ASA|SA|AS|aB|a }[/math]
[math]\displaystyle{ B \rightarrow b }[/math]
[math]\displaystyle{ S_0 \rightarrow ASA|SA|AS|aB|a }[/math] 
[math]\displaystyle{ A \rightarrow ASA|SA|AS|aB|a }[/math] 
[math]\displaystyle{ A \rightarrow b }[/math] 

Step 3

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

[math]\displaystyle{ S \rightarrow AS_1 }[/math]
[math]\displaystyle{ S_1 \rightarrow SA }[/math]
[math]\displaystyle{ A \rightarrow AA_1 }[/math]
[math]\displaystyle{ A_1 \rightarrow SA }[/math]

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

[math]\displaystyle{ A_2 \rightarrow a }[/math]
[math]\displaystyle{ S \rightarrow A_2B }[/math]

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

[math]\displaystyle{ S \rightarrow AS_1|SA|AS|A_2B|a }[/math]
[math]\displaystyle{ B \rightarrow b }[/math]
[math]\displaystyle{ S_0 \rightarrow AS_1|SA|AS|A_2B|a }[/math]
[math]\displaystyle{ A \rightarrow AA_1|SA|AS|A_2B|a }[/math] 
[math]\displaystyle{ A \rightarrow b }[/math] 
[math]\displaystyle{ A_2 \rightarrow a }[/math]