Chomsky Normal Form - 편집 역사

Pinkgo: /* Step 3 */

2025-11-13T08:04:23Z

Step 3

← 이전 판		2025년 11월 13일 (목) 08:04 판
46번째 줄:		46번째 줄:
	따라서 아래와 같이 최종적인 CNF가 도출된다:		따라서 아래와 같이 최종적인 CNF가 도출된다:
	<math>S \rightarrow AS_1\|SA\|AS\|A_2B\|a</math>		<math>S \rightarrow AS_1\|SA\|AS\|A_2B\|a</math>
			<math>S_0 \rightarrow AS_1\|SA\|AS\|A_2B\|a</math>
			<math>A \rightarrow AA_1\|SA\|AS\|A_2B\|a\|b</math>
	<math>B \rightarrow b</math>		<math>B \rightarrow b</math>
	<math>~~S_0~~ \rightarrow ~~AS_1\|~~SA~~\|AS\|A_2B\|a~~</math>		<math>S_1 \rightarrow SA</math>
	<math>A \rightarrow ~~AA_1\|~~SA~~\|AS\|A_2B\|a</math>~~		<math>A_1 \rightarrow SA</math>
	~~<math>A \rightarrow b~~</math>
	<math>A_2 \rightarrow a</math>		<math>A_2 \rightarrow a</math>

	==각주==		==각주==

Pinkgo: /* Step 2 */

2025-10-26T20:05:04Z

Step 2

← 이전 판		2025년 10월 26일 (일) 20:05 판
28번째 줄:		28번째 줄:
	<math>S \rightarrow AS</math>		<math>S \rightarrow AS</math>
	<math>S \rightarrow SA</math>		<math>S \rightarrow SA</math>
	또한, <math>A \rightarrow S, A \rightarrow B, S \rightarrow</math>와 같은 규칙 대신, 해당 변수들이 만들어낼 수 있는 규칙으로 대체해야 한다. 따라서 이를 일괄적으로 적용하면 아래와 같은 결과가 된다:		또한, <math>A \rightarrow S, A \rightarrow B, S \rightarrow S</math>와 같은 규칙 대신, 해당 변수들이 만들어낼 수 있는 규칙으로 대체해야 한다. 따라서 이를 일괄적으로 적용하면 아래와 같은 결과가 된다:
	<math>S \rightarrow ASA\|SA\|AS\|aB\|a</math>		<math>S \rightarrow ASA\|SA\|AS\|aB\|a</math>
	<math>B \rightarrow b</math>		<math>B \rightarrow b</math>

Pinkgo: /* CYK Algorithm */

2025-10-26T02:06:08Z

CYK Algorithm

@@ 51번째 줄: / 51번째 줄: @@
   <math>A \rightarrow b</math>
   <math>A_2 \rightarrow a</math>
 ==각주==

2025년 10월 26일 (일) 02:04에 Pinkgo님의 편집

2025-10-26T02:04:31Z

@@ 4번째 줄: / 4번째 줄: @@
 ==개요==
-CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다:
+CNF(Chomsky Normal Form)는 [[Grammars#Context-Free Languages|CFG]]를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법([[Grammars]])으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다:
 # <math>A \rightarrow BC</math><ref>이때 B, C는 시작 기호 S가 아니다</ref>
 # <math>A \rightarrow a</math>
@@ 51번째 줄: / 51번째 줄: @@
   <math>A \rightarrow b</math>
   <math>A_2 \rightarrow a</math>
 ==각주==

Pinkgo: /* Step 3 */

2025-10-26T01:42:52Z

Step 3

← 이전 판		2025년 10월 26일 (일) 01:42 판
51번째 줄:		51번째 줄:
	<math>A \rightarrow b</math>		<math>A \rightarrow b</math>
	<math>A_2 \rightarrow a</math>		<math>A_2 \rightarrow a</math>

			==각주==

Pinkgo: 새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다: # $A \rightarrow BC$ 이때 B, C는 시작 기호 S가 아니다...

2025-10-26T01:42:08Z

새 문서: 분류:계산 이론 개론 분류:컴퓨터 공학 상위 문서: Context-Free Languages ==개요== CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다: # <math>A \rightarrow BC</math><ref>이때 B, C는 시작 기호 S가 아니다...

새 문서

[[분류:계산 이론 개론]]
[[분류:컴퓨터 공학]]
상위 문서: [[Grammars#Context-Free Languages#Chomsky Normal Form|Context-Free Languages]]

==개요==
CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다. 모든 CFG는 CNF와 동등한 문법으로 바뀔 수 있으며, CFG가 다음 세 가지의 규칙만 가지면 CNF에 해당한다:
# <math>A \rightarrow BC</math><ref>이때 B, C는 시작 기호 S가 아니다</ref>
# <math>A \rightarrow a</math>
# <math>S \rightarrow \epsilon</math>
CFG를 CNF로 바꾸더라도 새로운 문자열이 생성되지는 않으며, 모든 grammar와 문자열이 그대로 보존된다.

==CFG to CNF==
아래와 같이 CFG가 주어졌다고 가정하자:
<math>S \rightarrow ASA | aB</math>
<math>A \rightarrow B | S</math>
<math>B \rightarrow b | \epsilon</math>

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

===Step 2===
주어진 식에 <math>B \rightarrow \epsilon</math>이 존재하므로 제거해야 한다. 이를 위해서 <math>B\rightarrow \epsilon</math> 규칙을 제거하고, <math>B</math>를 포함하는 식이 유도되는 모든 규칙에서, <math>B</math>를 <math>\epsilon</math>으로 치환한 아래의 식을 추가한다:
<math>S \rightarrow aB \rightarrow a</math>
<math>A \rightarrow B \rightarrow \epsilon</math>
위와 같은 과정을 <math>A \rightarrow \epsilon</math> 규칙에 대해서도 동일하게 적용해야 한다. 이를 위해 해당 식을 제거하고, 아래의 식들을 추가한다:
<math>S \rightarrow S</math>
<math>S \rightarrow AS</math>
<math>S \rightarrow SA</math>
또한, <math>A \rightarrow S, A \rightarrow B, S \rightarrow</math>와 같은 규칙 대신, 해당 변수들이 만들어낼 수 있는 규칙으로 대체해야 한다. 따라서 이를 일괄적으로 적용하면 아래와 같은 결과가 된다:
<math>S \rightarrow ASA|SA|AS|aB|a</math>
<math>B \rightarrow b</math>
<math>S_0 \rightarrow ASA|SA|AS|aB|a</math> <ref><math>S_0 \rightarrow S</math> 규칙을 삭제하며 추가</ref>
<math>A \rightarrow ASA|SA|AS|aB|a</math> <ref><math>A \rightarrow S</math> 규칙을 삭제하며 추가</ref>
<math>A \rightarrow b</math> <ref><math>A \rightarrow B</math> 규칙을 삭제하며 추가</ref>

===Step 3===
이제, CNF에서는 규칙의 오른쪽에 두개의 비단말만 가능하므로 3개 변수인 <math>ASA</math> 형태를 분해해야 한다. 이를 위해 해당 규칙을 아래와 같이 중간 비단말 <math>S_1, A_1</math>을 활용한 규칙들로 대체해야 한다.<ref>S_1, A_1과 같이 굳이 변수를 두개 추가하는 이유는 S에서 파생된 규칙과 A에서 파생된 규칙을 구분하기 위해서이다.</ref>:
<math>S \rightarrow AS_1</math>
<math>S_1 \rightarrow SA</math>
<math>A \rightarrow AA_1</math>
<math>A_1 \rightarrow SA</math>
또한, CNF에서는 단말이 반드시 단독으로만 나와야 하므로, <math>S \rightarrow aB</math>와 같은 규칙은 허용되지 않는다. 따라서 해당 규칙을 아래와 같이 중간 비단말 <math>A_2</math>을 활용한 규칙들로 대체해야 한다:
<math>A_2 \rightarrow a</math>
<math>S \rightarrow A_2B</math>
따라서 아래와 같이 최종적인 CNF가 도출된다:
<math>S \rightarrow AS_1|SA|AS|A_2B|a</math>
<math>B \rightarrow b</math>
<math>S_0 \rightarrow AS_1|SA|AS|A_2B|a</math>
<math>A \rightarrow AA_1|SA|AS|A_2B|a</math>
<math>A \rightarrow b</math>
<math>A_2 \rightarrow a</math>