Regular Languages - 편집 역사

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

2026-01-15T15:24:05Z

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

← 이전 판		2026년 1월 15일 (목) 15:24 판
1번째 줄:		1번째 줄:
	[[분류:계산 이론 개론]]		[[분류:계산 이론 개론]]
	~~[[분류:컴퓨터 공학]]~~

	상위 문서: [[Finite Automata#Finite Automata as Language Recognizers#Formal Definition of Finite Automaton\|Finite Automata]]		상위 문서: [[Finite Automata#Finite Automata as Language Recognizers#Formal Definition of Finite Automaton\|Finite Automata]]

Pinkgo: /* The Pumping Lemma */

2025-10-30T05:08:02Z

The Pumping Lemma

@@ 133번째 줄: / 133번째 줄: @@
 자세한 내용은 [[Regular Expressions]] 문서를 참조하십시오.
-==The Pumping Lemma==
+==[[Pumping Lemma]]==
-DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:
+[[Pumping Lemma]]에 대한 자세한 설명은 해당 문서를 참조하십시오.
 ==[[Grammars]]==

Pinkgo: /* Grammars */

2025-10-17T18:49:25Z

Grammars

← 이전 판		2025년 10월 17일 (금) 18:49 판
161번째 줄:		161번째 줄:
	# 하지만 0과 1의 개수가 다르므로 <math>xy^0z = 0^{p-k}1^p</math>는 B에 속하지 않고, 모순이 발생한다.		# 하지만 0과 1의 개수가 다르므로 <math>xy^0z = 0^{p-k}1^p</math>는 B에 속하지 않고, 모순이 발생한다.
	위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.		위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.

	~~==[[Grammars]]==~~
	~~자세한 내용은 [[Grammars]] 문서를 참조해주십시오.~~

	===Using Other Facts with the PL===		===Using Other Facts with the PL===
174번째 줄:		171번째 줄:
	* PL에 따라 <math>\|xy\|\le p</math>이므로 <math>y</math>는 오직 0으로만 이루어 져야 한다.(<math>y=0^k</math>)		* PL에 따라 <math>\|xy\|\le p</math>이므로 <math>y</math>는 오직 0으로만 이루어 져야 한다.(<math>y=0^k</math>)
	* 따라서 <math>xy^0z = 0^{p-k}1^p2^{2p}</math>가 되어야 하는데, 이는 <math>L \cap 012*</math>에 속하지 않는다.		* 따라서 <math>xy^0z = 0^{p-k}1^p2^{2p}</math>가 되어야 하는데, 이는 <math>L \cap 012*</math>에 속하지 않는다.

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

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

Pinkgo: /* Applying the Pumping Lemma */

2025-10-17T18:49:09Z

Applying the Pumping Lemma

← 이전 판		2025년 10월 17일 (금) 18:49 판
161번째 줄:		161번째 줄:
	# 하지만 0과 1의 개수가 다르므로 <math>xy^0z = 0^{p-k}1^p</math>는 B에 속하지 않고, 모순이 발생한다.		# 하지만 0과 1의 개수가 다르므로 <math>xy^0z = 0^{p-k}1^p</math>는 B에 속하지 않고, 모순이 발생한다.
	위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.		위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.

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

	===Using Other Facts with the PL===		===Using Other Facts with the PL===

Pinkgo: /* Non-Regular Languages */

2025-10-17T18:47:34Z

Non-Regular Languages

← 이전 판		2025년 10월 17일 (금) 18:47 판
133번째 줄:		133번째 줄:
	자세한 내용은 [[Regular Expressions]] 문서를 참조하십시오.		자세한 내용은 [[Regular Expressions]] 문서를 참조하십시오.

	~~==Non-Regular Languages==~~
	==The Pumping Lemma==		==The Pumping Lemma==
	DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:		DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:

Pinkgo: /* The Pumping Lemma */

2025-10-08T22:16:06Z

The Pumping Lemma

← 이전 판		2025년 10월 8일 (수) 22:16 판
143번째 줄:		143번째 줄:
	이를 논리식으로 나타내면 아래와 같다:		이를 논리식으로 나타내면 아래와 같다:
	<math>\forall L\,\,regular \rightarrow</math>		<math>\forall L\,\,regular \rightarrow</math>
	<math>\qquad\exist p. \forall w. w\in L \land \|w\| ~~\ge p~~ \rightarrow</math>		<math>\qquad\exist p. \forall w. w\in L \land p \le \|w\| \rightarrow</math>
	<math>\qquad\qquad\exist x\,\,y\,\,z. w =xyz \land (1) \land (2) \land (3)</math>		<math>\qquad\qquad\exist x\,\,y\,\,z. w =xyz \land (1) \land (2) \land (3)</math>
	먼저, 1번 조건은 y 부분을 0번, 1번, 2번… 아무 번이든 반복해도 여전히 언어 L에 속해야 한다는 것을 의미한다. 예를 들어 <math>i=0</math>일때 <math>xz</math>, <math>i=1</math>일때 <math>xyz</math>, <math>i=2</math>일때 <math>xyyz</math> 등등이 모두 L에 속해야 한다는 것이다.<br>		먼저, 1번 조건은 y 부분을 0번, 1번, 2번… 아무 번이든 반복해도 여전히 언어 L에 속해야 한다는 것을 의미한다. 예를 들어 <math>i=0</math>일때 <math>xz</math>, <math>i=1</math>일때 <math>xyz</math>, <math>i=2</math>일때 <math>xyyz</math> 등등이 모두 L에 속해야 한다는 것이다.<br>

Pinkgo: /* The Pumping Lemma */

2025-10-08T21:57:29Z

The Pumping Lemma

← 이전 판		2025년 10월 8일 (수) 21:57 판
136번째 줄:		136번째 줄:
	==The Pumping Lemma==		==The Pumping Lemma==
	DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:		DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:
	L이 정규언어라면, 어떤 펌핑 길이 p가 존재한다.~~(p는 DFA의 상태의 개수이다.)~~		L이 정규언어라면, 어떤 펌핑 길이 p가 존재한다.
	이때 길이가 p 이상인 모든 문자열은 세 부분 x, y, z로 분해할 수 있으며, 아래 조건을 만족한다.		이때 길이가 p 이상인 모든 문자열은 세 부분 x, y, z로 분해할 수 있으며, 아래 조건을 만족한다.
	1. <math>\forall i \ge 0. xy^iz \in L</math>		1. <math>\forall i \ge 0. xy^iz \in L</math>

Pinkgo: /* The Regular Operations */

2025-10-08T13:12:06Z

The Regular Operations

← 이전 판		2025년 10월 8일 (수) 13:12 판
63번째 줄:		63번째 줄:
	* Union: <math>A \cup B = \{x\|x\in A \lor x \in B\} </math>		* Union: <math>A \cup B = \{x\|x\in A \lor x \in B\} </math>
	** 즉, 언어 A 또는 언어 B 중 하나에 속하는 모든 문자열을 의미한다.		** 즉, 언어 A 또는 언어 B 중 하나에 속하는 모든 문자열을 의미한다.
	* Concatenation: <math>A \circ B = \{xy\|x\in \land y\in B\}</math>		* Concatenation: <math>A \circ B = \{xy\|x\in A\land y\in B\}</math>
	** 즉, A의 원소와 B의 원소를 이어붙인 문자열만을 포함하는 집합이다.		** 즉, A의 원소와 B의 원소를 이어붙인 문자열만을 포함하는 집합이다.
	** 더욱 엄밀히 기술하면, <math>A \circ B = \{w\|\exists x,y. w=xy \land x \in A \and y \in B\}</math>		** 더욱 엄밀히 기술하면, <math>A \circ B = \{w\|\exists x,y. w=xy \land x \in A \and y \in B\}</math>

Pinkgo: /* Example Problem */

2025-10-08T13:07:11Z

Example Problem

← 이전 판		2025년 10월 8일 (수) 13:07 판
34번째 줄:		34번째 줄:

	===Example Problem===		===Example Problem===
			[[파일:Figure 3. Given Diagram.png\|섬네일\|Figure 3. Given Diagram]]
	위에 대해 이해하기 위해, figure 3를 참고하여 아래와 같은 문제를 풀어보자:		위에 대해 이해하기 위해, figure 3를 참고하여 아래와 같은 문제를 풀어보자:
	Consider the example FA,		Consider the example FA,

Pinkgo: /* Applying the Pumping Lemma */

2025-10-07T04:07:11Z

Applying the Pumping Lemma

← 이전 판		2025년 10월 7일 (화) 04:07 판
158번째 줄:		158번째 줄:
	# 이때 B는 정규언어이므로, 조건에 따라 <math>w = xyz</math>로 분해된다.		# 이때 B는 정규언어이므로, 조건에 따라 <math>w = xyz</math>로 분해된다.
	# 이때 <math>\|xy\| \le p</math>이므로, y는 반드시 0으로만 구성된다. <math>0 < k \le p.\,\,y = 0^k</math>		# 이때 <math>\|xy\| \le p</math>이므로, y는 반드시 0으로만 구성된다. <math>0 < k \le p.\,\,y = 0^k</math>
	# 이때 <math>x = 0^{p-k}, 1^p</math>이므로, pumping lemma에 따라 이때 <math>xy^0z = 0^{p-k}1^p</math>도 B에 속해야 한다.		# 이때 <math>x = 0^{p-k}, z=1^p</math>이므로, pumping lemma에 따라 이때 <math>xy^0z = 0^{p-k}1^p</math>도 B에 속해야 한다.
	# 하지만 0과 1의 개수가 다르므로 <math>xy^0z = 0^{p-k}1^p</math>는 B에 속하지 않고, 모순이 발생한다.		# 하지만 0과 1의 개수가 다르므로 <math>xy^0z = 0^{p-k}1^p</math>는 B에 속하지 않고, 모순이 발생한다.
	위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.		위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.