Grammars - 편집 역사

Ahn9807: 봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

2026-01-15T15:21:25Z

봇: 자동으로 텍스트 교체 (-\[\[분류:컴퓨터 공학(\|[^\]]+)?\]\] +)

← 이전 판		2026년 1월 15일 (목) 15:21 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~
	상위 문서: [[Regular Languages#Grammars\|Regular Languages]]		상위 문서: [[Regular Languages#Grammars\|Regular Languages]]

Pinkgo: /* Classes of Grammars */

2025-11-12T23:56:01Z

Classes of Grammars

← 이전 판		2025년 11월 12일 (수) 23:56 판
14번째 줄:		14번째 줄:
	#* 문맥과 상관없이 하나의 비단말기만 보고 규칙을 적용할 수 있다.		#* 문맥과 상관없이 하나의 비단말기만 보고 규칙을 적용할 수 있다.
	#* PDA(푸시다운 오토마톤)과 동일한 계산 능력을 가진다.		#* PDA(푸시다운 오토마톤)과 동일한 계산 능력을 가진다.
	# Regular Grammar: CFG보다 더욱 단순한 형태이다.		# Regular Grammar: CFG보다 더욱 단순한 형태이다. 기본적으로 CFG에 속한다.
	#* 각 규칙은 <math>r = w</math>또는 <math>r = wB</math>꼴이며, 오른쪽 끝에 비단말기가 올 수 있다.		#* 각 규칙은 <math>r = w</math>또는 <math>r = wB</math>꼴이며, 오른쪽 끝에 비단말기가 올 수 있다.
	#* 이는 이름에서 짐작할 수 있듯이 정규언어와 정확히 동일한 클래스이다.		#* 이는 이름에서 짐작할 수 있듯이 정규언어와 정확히 동일한 클래스이다.

Pinkgo: /* Context-Free Languages */

2025-11-10T19:46:12Z

Context-Free Languages

← 이전 판		2025년 11월 10일 (월) 19:46 판
110번째 줄:		110번째 줄:

	===[[Chomsky Normal Form]]===		===[[Chomsky Normal Form]]===
	CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다.		CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다.<br>

	[[Chomsky Normal Form\|CNF(Chomsky Normal Form)]]에 대한 자세한 정보는 해당 문서를 참조해 주십시오.		[[Chomsky Normal Form\|CNF(Chomsky Normal Form)]]에 대한 자세한 정보는 해당 문서를 참조해 주십시오.

	===[[CYK Algorithm]]===		===[[CYK Algorithm]]===
	CYK(Cocke–Younger–Kasami) 알고리즘은 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.		CYK(Cocke–Younger–Kasami) 알고리즘은 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.<br>

	자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.		자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.

	===[[Pushdown Automaton]]===		===[[Pushdown Automaton]]===
	정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.		정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.<br>

	자세한 설명은 [[Pushdown Automaton]] 문서를 참조해 주십시오.		자세한 설명은 [[Pushdown Automaton]] 문서를 참조해 주십시오.

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

Pinkgo: /* Chomsky Normal Form */

2025-11-10T19:45:26Z

Chomsky Normal Form

← 이전 판		2025년 11월 10일 (월) 19:45 판
109번째 줄:		109번째 줄:
	이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.		이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.

	===Chomsky Normal Form===		===[[Chomsky Normal Form]]===
	CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다.		CNF(Chomsky Normal Form)는 CFG를 더욱 간단하고 증명하기 쉽게 바꾼 표준 형식이다.

Pinkgo: /* Pushdown Automaton */

2025-10-30T04:42:32Z

Pushdown Automaton

← 이전 판		2025년 10월 30일 (목) 04:42 판
119번째 줄:		119번째 줄:
	자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.		자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.

	==[[Pushdown Automaton]]==		===[[Pushdown Automaton]]===
	정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.		정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.

Pinkgo: /* Context-Free Languages */

2025-10-30T04:38:51Z

Context-Free Languages

← 이전 판		2025년 10월 30일 (목) 04:38 판
104번째 줄:		104번째 줄:
	Regular Languages <math>\subseteq</math> Context-Free Languages		Regular Languages <math>\subseteq</math> Context-Free Languages
	이는 정규언어보다 CFL의 표현력이 더 강하다는 것을 의미한다. 예를 들어 <math>L=\{0^n1^n\|n\ge 0\}</math>과 같은 언어는 정규언어가 아니지만 CFG로는 표현 가능하다. 따라서 아래와 같은 명제가 성립한다.		이는 정규언어보다 CFL의 표현력이 더 강하다는 것을 의미한다. 예를 들어 <math>L=\{0^n1^n\|n\ge 0\}</math>과 같은 언어는 정규언어가 아니지만 CFG로는 표현 가능하다. 따라서 아래와 같은 명제가 성립한다.
	<math>CFL \cap Regular\,\,Language \~~supseteq~~ CFL</math>		<math>CFL \cap Regular\,\,Language \subseteq CFL</math>
	또한 아래와 같은 명제가 성립한다:		이는 어떠한 언어가 CFL이기도 하면서, 정규 언어이기도 한다면 CFL에 속한다는 것을 의미한다. 또한 아래와 같은 명제가 성립한다:
	The class of context-free languages is closed under <math>\cup, \circ, *</math>.		The class of context-free languages is closed under <math>\cup, \circ, *</math>.
	이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.		이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.

Pinkgo: /* Context-Free Languages */

2025-10-30T04:37:08Z

Context-Free Languages

← 이전 판		2025년 10월 30일 (목) 04:37 판
103번째 줄:		103번째 줄:
	이때 모든 정규언어는 context-free이다. 이는 모든 정규 언어는 항상 regular grammar로 표현될 수 있는데, 모든 정규 문법은 문맥자유문법의 특수한 형태이기 때문이다. 즉, 아래와 같은 명제가 성립한다.		이때 모든 정규언어는 context-free이다. 이는 모든 정규 언어는 항상 regular grammar로 표현될 수 있는데, 모든 정규 문법은 문맥자유문법의 특수한 형태이기 때문이다. 즉, 아래와 같은 명제가 성립한다.
	Regular Languages <math>\subseteq</math> Context-Free Languages		Regular Languages <math>\subseteq</math> Context-Free Languages
	이는 정규언어보다 CFL의 표현력이 더 강하다는 것을 의미한다. 예를 들어 <math>L=\{0^n1^n\|n\ge 0\}</math>과 같은 언어는 정규언어가 아니지만 CFG로는 표현 가능하다. 또한 아래와 같은 명제가 성립한다:		이는 정규언어보다 CFL의 표현력이 더 강하다는 것을 의미한다. 예를 들어 <math>L=\{0^n1^n\|n\ge 0\}</math>과 같은 언어는 정규언어가 아니지만 CFG로는 표현 가능하다. 따라서 아래와 같은 명제가 성립한다.
			<math>CFL \cap Regular\,\,Language \supseteq CFL</math>
			또한 아래와 같은 명제가 성립한다:
	The class of context-free languages is closed under <math>\cup, \circ, *</math>.		The class of context-free languages is closed under <math>\cup, \circ, *</math>.
	이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.		이는 정규언어와 마찬가지로 CFL <math>L_1, L_2</math>에 대해, <math>L_1\cup L_2,\,\, L_1L_2,\,\, L_1*</math>도 모두 CFL이라는 것을 의미한다.

Pinkgo: /* =Pushdown Automaton */

2025-10-26T04:34:07Z

=Pushdown Automaton

← 이전 판		2025년 10월 26일 (일) 04:34 판
117번째 줄:		117번째 줄:
	자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.		자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.

	===[[Pushdown Automaton]]==		==[[Pushdown Automaton]]==
	정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.		정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.

Pinkgo: /* CYK Algorithm */

2025-10-26T04:33:58Z

CYK Algorithm

← 이전 판		2025년 10월 26일 (일) 04:33 판
116번째 줄:		116번째 줄:

	자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.		자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.

			===[[Pushdown Automaton]]==
			정규 언어를 다루기 위해서는 Finite Automaton으로 충분하지만, 그보다 더 일반적인 언어인 CFG를 다루기 위해서는 Pushdown Automaton이 사용된다.

			자세한 설명은 [[Pushdown Automaton]] 문서를 참조해 주십시오.

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

Pinkgo: /* CYK Algorithm */

2025-10-26T02:10:27Z

CYK Algorithm

← 이전 판		2025년 10월 26일 (일) 02:10 판
113번째 줄:		113번째 줄:

	===[[CYK Algorithm]]===		===[[CYK Algorithm]]===
	~~[[CYK Algorithm\|~~CYK(Cocke–Younger–Kasami) ~~알고리즘]]은~~ CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.		CYK(Cocke–Younger–Kasami) 알고리즘은 CFL(Context-Free Language)를 인식하기 위한 동적 프로그래밍 기반의 알고리즘이다.

	자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.		자세한 내용은 [[CYK Algorithm]] 문서를 참조해 주십시오.

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