Pumping Lemma - 편집 역사

Pinkgo: /* Using Other Facts with the PL */

2025-11-12T23:21:35Z

Using Other Facts with the PL

← 이전 판		2025년 11월 12일 (수) 23:21 판
35번째 줄:		35번째 줄:
	Pumping Lemma를 직접 적용하기 전에, 정규언어에 대한 다른 성질(closure property) 을 함께 이용하면 증명이 쉬워진다. 아래와 같은 언어가 비정규 언어라는 것을 증명해보자:		Pumping Lemma를 직접 적용하기 전에, 정규언어에 대한 다른 성질(closure property) 을 함께 이용하면 증명이 쉬워진다. 아래와 같은 언어가 비정규 언어라는 것을 증명해보자:
	<math>L=\{w\in \{0,1,2\}*\|\#0(w)+\#(1)=\#(2)\}</math>		<math>L=\{w\in \{0,1,2\}*\|\#0(w)+\#(1)=\#(2)\}</math>
	위 언어는 자열 안의 0과 1의 개수의 합이 2의 개수와 같아야 하는 언어이다. 위 언어가 비정규임을 보이기 위해, L이 정규라고 가정하자. 또한 정규언어는 교집합에 대해 닫혀 있음(closure under intersection)을 이용하면, 아래와 같은 언어 또한 정규 언어이다:		위 언어는 문자열 안의 0과 1의 개수의 합이 2의 개수와 같아야 하는 언어이다. 위 언어가 비정규임을 보이기 위해, L이 정규라고 가정하자. 또한 정규언어는 교집합에 대해 닫혀 있음(closure under intersection)을 이용하면, 아래와 같은 언어 또한 정규 언어이다:
	<math>L \cap 012* = \{0^m1^n2^{m+n}\|m\ge0,n\ge0\}</math>		<math>L \cap 012* = \{0^m1^n2^{m+n}\|m\ge0,n\ge0\}</math>
	이때 pumping lemma를 위 교집합 언어에 적용해보자:		이때 pumping lemma를 위 교집합 언어에 적용해보자:

Pinkgo: /* Using Other Facts with the PL */

2025-11-12T23:09:59Z

Using Other Facts with the PL

← 이전 판		2025년 11월 12일 (수) 23:09 판
38번째 줄:		38번째 줄:
	<math>L \cap 012* = \{0^m1^n2^{m+n}\|m\ge0,n\ge0\}</math>		<math>L \cap 012* = \{0^m1^n2^{m+n}\|m\ge0,n\ge0\}</math>
	이때 pumping lemma를 위 교집합 언어에 적용해보자:		이때 pumping lemma를 위 교집합 언어에 적용해보자:
	* 펌핑 길이를 p라고 하고, <math>w = 0^p0^p2^p</math>를 선택한다.		* 펌핑 길이를 p라고 하고, <math>w = 0^p0^p2^{2p}</math>를 선택한다.
	* 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>에 속하지 않는다.

Pinkgo: /* Applying the Pumping Lemma for CFLs */

2025-11-10T20:03:57Z

Applying the Pumping Lemma for CFLs

← 이전 판		2025년 11월 10일 (월) 20:03 판
68번째 줄:		68번째 줄:
	# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우		# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.		#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.
	#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다. #* 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.		#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다.
			#* 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.
	# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우		# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.		#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.

Pinkgo: /* Applying the Pumping Lemma for CFLs */

2025-11-10T20:03:16Z

Applying the Pumping Lemma for CFLs

← 이전 판		2025년 11월 10일 (월) 20:03 판
68번째 줄:		68번째 줄:
	# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우		# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.		#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.
	#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다. 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.		#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다. #* 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.
	# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우		# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.		#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.

Pinkgo: /* Applying the Pumping Lemma for CFLs */

2025-11-10T20:02:46Z

Applying the Pumping Lemma for CFLs

← 이전 판		2025년 11월 10일 (월) 20:02 판
64번째 줄:		64번째 줄:
	#* <math>\|vy\|>0</math>		#* <math>\|vy\|>0</math>
	#* <math>\|vxy\| \le p</math>		#* <math>\|vxy\| \le p</math>
			[[파일:Figure 1. s의 문자열 구조.png\|섬네일\|200x200픽셀\|Figure 1. s의 문자열 구조]]
	해당 단계 까지 진행하였다면 핵심은 모든 가능한 <math>vxy</math>의 위치에 대해서 <math>i\ne 1</math>일 때 문자열이 L에 속하지 않음을 보이는 것이다. 이를 보이기 위해서는 <math>vxy</math>가 <math>s = 0^p1^p0^p1^p</math>에서 어디에 위치할 수 있는지를 세 가지로 나누어 설명해야 한다. Figure 1은 L의 문자열 구조이며, 케이스를 나눌 때의 이해를 돕기 위한 이미지이다. 이때 가능한 케이스는 <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우,<ref>즉, figure 1의 첫 번째 또는 두 번째 블록 안에 존재하는 경우이다.</ref> <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우,<ref>즉, 즉, figure 1의 세 번째 또는 네 번째 블록 안에 존재하는 경우이다.</ref> <math>vxy</math>가 중간 경계 <math>1^p0^p</math>를 걸치는 경우<ref>즉, 즉, figure 1의 앞의 1 블록과 뒤의 0 블록에 걸쳐 있는 부분에 존재하는 경우이다.</ref>이다. 이 세가지 경우만 고려하면 되는 이유는 <math>\|vxy\|\le p</math>이므로, 주어진 문자열 길이의 절반을 넘을 수 없기 때문이다. 각각의 경우를 살펴보면 아래와 같다:		해당 단계 까지 진행하였다면 핵심은 모든 가능한 <math>vxy</math>의 위치에 대해서 <math>i\ne 1</math>일 때 문자열이 L에 속하지 않음을 보이는 것이다. 이를 보이기 위해서는 <math>vxy</math>가 <math>s = 0^p1^p0^p1^p</math>에서 어디에 위치할 수 있는지를 세 가지로 나누어 설명해야 한다. Figure 1은 L의 문자열 구조이며, 케이스를 나눌 때의 이해를 돕기 위한 이미지이다. 이때 가능한 케이스는 <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우,<ref>즉, figure 1의 첫 번째 또는 두 번째 블록 안에 존재하는 경우이다.</ref> <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우,<ref>즉, 즉, figure 1의 세 번째 또는 네 번째 블록 안에 존재하는 경우이다.</ref> <math>vxy</math>가 중간 경계 <math>1^p0^p</math>를 걸치는 경우<ref>즉, 즉, figure 1의 앞의 1 블록과 뒤의 0 블록에 걸쳐 있는 부분에 존재하는 경우이다.</ref>이다. 이 세가지 경우만 고려하면 되는 이유는 <math>\|vxy\|\le p</math>이므로, 주어진 문자열 길이의 절반을 넘을 수 없기 때문이다. 각각의 경우를 살펴보면 아래와 같다:
	# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우		# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.		#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.
	#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다. 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.		#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다. 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.
	# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우		# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.		#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.
	#* 따라서 pumping 후에는 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.		#* 따라서 pumping 후에는 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.
	# Case 3: <math>vxy</math>가 중간 경계 <math>1^p0^p</math>를 걸치는 경우		# Case 3: <math>vxy</math>가 중간 경계 <math>1^p0^p</math>를 걸치는 경우

Pinkgo: /* Applying the Pumping Lemma for CFLs */

2025-10-30T06:08:26Z

Applying the Pumping Lemma for CFLs

← 이전 판		2025년 10월 30일 (목) 06:08 판
53번째 줄:		53번째 줄:

	===Applying the Pumping Lemma for CFLs===		===Applying the Pumping Lemma for CFLs===
			CFL에 대한 PL은 일반적인 PL과 마찬가지로 주어진 언어가 CFL이 아님을 증명하는데 사용할 수 있다. 예를 들어 아래와 같은 언어가 주어졌다고 가정하자:
	<math></math>		<math>L = \{ww\|w\in \{0,1\}*\}</math>
	<math></math>		위 언어는 어떤 문자열 w를 두 번 반복한 것들의 집합으로, 00, 0101, 1010, 11001100 등이 L에 속한다. 이 언어가 CFL이 아니라는 것은 아래와 같은 과정을 통해서 증명할 수 있다:
	<math></math>		# L이 context-free라고 가정하자.
	<math></math>		# Pumping Lemma에 의해 어떤 일정한 길이 p가 존재한다.
	<math></math>		# Pumping Lemma를 적용하기 위해서는 <math>\|s\|\le p</math>를 만족하는 어떤 문자열 <math>s\in L</math>이 필요하다.
	<math></math>		#* 이에 따라 <math>s = 0^p1^p0^p1^p</math>를 선택하며, 해당 문자열은 명백히 <math>L</math>에 속한다.
	<math></math>		# 문자열 <math>s</math>에 대해 pumping lemma를 적용하면, <math>s = uvxyz</math>와 같이 나타내어지며, 아래 조건을 만족한다:
	<math></math>		#* <math>uv^ixy^iz \in L,\forall i\ge 0</math>
	<math></math>		#* <math>\|vy\|>0</math>
	<math></math>		#* <math>\|vxy\| \le p</math>
	<math></math>		해당 단계 까지 진행하였다면 핵심은 모든 가능한 <math>vxy</math>의 위치에 대해서 <math>i\ne 1</math>일 때 문자열이 L에 속하지 않음을 보이는 것이다. 이를 보이기 위해서는 <math>vxy</math>가 <math>s = 0^p1^p0^p1^p</math>에서 어디에 위치할 수 있는지를 세 가지로 나누어 설명해야 한다. Figure 1은 L의 문자열 구조이며, 케이스를 나눌 때의 이해를 돕기 위한 이미지이다. 이때 가능한 케이스는 <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우,<ref>즉, figure 1의 첫 번째 또는 두 번째 블록 안에 존재하는 경우이다.</ref> <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우,<ref>즉, 즉, figure 1의 세 번째 또는 네 번째 블록 안에 존재하는 경우이다.</ref> <math>vxy</math>가 중간 경계 <math>1^p0^p</math>를 걸치는 경우<ref>즉, 즉, figure 1의 앞의 1 블록과 뒤의 0 블록에 걸쳐 있는 부분에 존재하는 경우이다.</ref>이다. 이 세가지 경우만 고려하면 되는 이유는 <math>\|vxy\|\le p</math>이므로, 주어진 문자열 길이의 절반을 넘을 수 없기 때문이다. 각각의 경우를 살펴보면 아래와 같다:
	<math></math>		# Case 1: <math>vxy</math>가 첫 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	<math></math>		#* pumping을 하면 첫 절반이 변하고 두 번째 절반은 그대로 남는다.
	<math></math>		#* 예를 들어, <math>uv^2xy^2z</math>는 <math>uvxyz</math>에 비해서 앞 절반의 길이나 내용이 달라졌으나, 뒤 절반은 변하지 않는다. 따라서 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.
	<math></math>		# Case 2: <math>vxy</math>가 두 번째 절반 <math>0^p1^p</math> 안에 완전히 포함되는 경우
	<math></math>		#* 이번엔 반대로, 두 번째 절반이 변하고 첫 절반은 그대로 남는다.
	<math></math>		#* 따라서 pumping 후에는 앞과 뒤가 더 이상 동일하지 않게되므로 <math>uv^2xy^2z\notin L</math>이다.
	<math></math>		# Case 3: <math>vxy</math>가 중간 경계 <math>1^p0^p</math>를 걸치는 경우
	<math></math>		#* 이 경우에 <math>v, y</math>를 pump하면 “1 일부와 0 일부”가 동시에 변한다.
	<math></math>		#* 예를 들어, <math>i=0</math>일 때에는 앞 부분의 일부 1과 뒷 부분의 일부 0이 삭제되어서 앞과 뒤가 더 이상 동일하지 않는다.
	<math></math>		#* 따라서 <math>uv^0xy^0z\notin L</math>이다.
	<math></math>		따라서, 어떤 경우에도 pumping 후의 문자열은 L에 속하지 않는다. 이것은 Pumping Lemma의 조건 1을 위반하므로 모순이 발생한다.
	<math></math>
	<math></math>
	<math></math>
	<math></math>

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

Pinkgo: /* = */

2025-10-30T05:34:21Z

← 이전 판		2025년 10월 30일 (목) 05:34 판
54번째 줄:		54번째 줄:
	===Applying the Pumping Lemma for CFLs===		===Applying the Pumping Lemma for CFLs===

	~~===~~
	<math></math>		<math></math>
	<math></math>		<math></math>

Pinkgo: /* Pumping Lemma for CFLs */

2025-10-30T05:34:13Z

Pumping Lemma for CFLs

← 이전 판		2025년 10월 30일 (목) 05:34 판
51번째 줄:		51번째 줄:
	# <math>\|vxy\| \le p</math>: v, x, y의 길이는 일정한 상한 p 이하이다.		# <math>\|vxy\| \le p</math>: v, x, y의 길이는 일정한 상한 p 이하이다.
	위 개념을 구체화하기 위해서 어떤 CFG <math>G = (V,\Sigma, R, S)</math>와, 해당 문법에서 <math>L=L(G)</math>를 도입하자. 또한 <math>G</math>에서의 한 [[Grammars#Definition of Grammars#Parse Trees\|parse tree]]의 높이가 h일 때, 각 노드의 자식 수가 최대 b라고 하자.<ref>주어진 규칙의 RHS 길이의 최댓값을 의미한다.</ref> 이 경우 트리의 leaf 노드의 수<ref>단말기 수의 최댓값을 의미한다.</ref>는 최대 <math>b^h</math>개이다. 따라서 문자열 s가 <math>\|s\|>b^h</math>이면 해당 문자열을 만드는 parse tree의 높이는 h보다 커야 한다. 즉, 이는 긴 문자열은 필연적으로 높은 트리(깊은 유도)를 가져야 한다는 것을 의미한다. 이제 변수의 개수가 <math>\|V\|</math>라고 할때, 트리의 경로를 따라가다 높이가 <math>\|V\|+1</math> 이상에 도달하면 어떠한 변수는 반드시 두 번 이상 등장해야 한다. 이 “두 번 등장한 변수”가 바로 pumping의 근거가 되는 것이다.		위 개념을 구체화하기 위해서 어떤 CFG <math>G = (V,\Sigma, R, S)</math>와, 해당 문법에서 <math>L=L(G)</math>를 도입하자. 또한 <math>G</math>에서의 한 [[Grammars#Definition of Grammars#Parse Trees\|parse tree]]의 높이가 h일 때, 각 노드의 자식 수가 최대 b라고 하자.<ref>주어진 규칙의 RHS 길이의 최댓값을 의미한다.</ref> 이 경우 트리의 leaf 노드의 수<ref>단말기 수의 최댓값을 의미한다.</ref>는 최대 <math>b^h</math>개이다. 따라서 문자열 s가 <math>\|s\|>b^h</math>이면 해당 문자열을 만드는 parse tree의 높이는 h보다 커야 한다. 즉, 이는 긴 문자열은 필연적으로 높은 트리(깊은 유도)를 가져야 한다는 것을 의미한다. 이제 변수의 개수가 <math>\|V\|</math>라고 할때, 트리의 경로를 따라가다 높이가 <math>\|V\|+1</math> 이상에 도달하면 어떠한 변수는 반드시 두 번 이상 등장해야 한다. 이 “두 번 등장한 변수”가 바로 pumping의 근거가 되는 것이다.

			===Applying the Pumping Lemma for CFLs===

	===		===

Pinkgo: /* Pumping Lemma for CFLs */

2025-10-30T05:33:52Z

Pumping Lemma for CFLs

@@ 50번째 줄: / 50번째 줄: @@
 # <math>|vy|>0</math>: v와 y 중 적어도 하나는 비어 있지 않아야 한다.<ref>즉, 실제로 뭔가 반복 가능한 부분이 존재해야 한다.</ref>
 # <math>|vxy| \le p</math>: v, x, y의 길이는 일정한 상한 p 이하이다.
 <math></math>
 <math></math>

2025년 10월 30일 (목) 05:14에 Pinkgo님의 편집

2025-10-30T05:14:16Z

← 이전 판		2025년 10월 30일 (목) 05:14 판
20번째 줄:		20번째 줄:
	Pumping Lemma를 다른 말로 표현하면, <math>L\subseteq\{1\}*</math>이 정규 언어라면 <math>L</math>의 문자열 길이들의 집합은 등차수열을 포함한다는 것이다.		Pumping Lemma를 다른 말로 표현하면, <math>L\subseteq\{1\}*</math>이 정규 언어라면 <math>L</math>의 문자열 길이들의 집합은 등차수열을 포함한다는 것이다.

	===Applying the Pumping Lemma===		==Applying the Pumping Lemma==
	이는 어떤 언어가 정규언어는 아니라는 것을 보이는 데에 사용된다. 예를 들어, 아래와 같은 언어를 고려하자:		이는 어떤 언어가 정규언어는 아니라는 것을 보이는 데에 사용된다. 예를 들어, 아래와 같은 언어를 고려하자:
	<math>B = \{0^n1^n\|n\ge 0\}</math>		<math>B = \{0^n1^n\|n\ge 0\}</math>
32번째 줄:		32번째 줄:
	위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.		위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.

	===Using Other Facts with the PL===		==Using Other Facts with the PL==
	Pumping Lemma를 직접 적용하기 전에, 정규언어에 대한 다른 성질(closure property) 을 함께 이용하면 증명이 쉬워진다. 아래와 같은 언어가 비정규 언어라는 것을 증명해보자:		Pumping Lemma를 직접 적용하기 전에, 정규언어에 대한 다른 성질(closure property) 을 함께 이용하면 증명이 쉬워진다. 아래와 같은 언어가 비정규 언어라는 것을 증명해보자:
	<math>L=\{w\in \{0,1,2\}*\|\#0(w)+\#(1)=\#(2)\}</math>		<math>L=\{w\in \{0,1,2\}*\|\#0(w)+\#(1)=\#(2)\}</math>
42번째 줄:		42번째 줄:
	* 따라서 <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>에 속하지 않는다.

			==Pumping Lemma for CFLs==
			PL은 [[Grammars#Context-Free Languages\|CFL(Context-Free Language)]]에도 적용할 수 있다. 이는 아래와 같다:
			만약 L이 CFL이라면, 충분히 긴 문자열 <math>s\in L</math>에 대해 <math>s</math>를 아래와 같이 5부분으로 나눌 수 있다:
			<math>s=uvxyz</math>
			이때 아래의 세 조건이 항상 성립한다:
			# <math>uv^ixy^iz \in L,\forall i\ge 0</math>: 즉, v와 y 부분을 “반복(pumping)”해도 여전히 L 안에 속한다.
			# <math>\|vy\|>0</math>: v와 y 중 적어도 하나는 비어 있지 않아야 한다.<ref>즉, 실제로 뭔가 반복 가능한 부분이 존재해야 한다.</ref>
			# <math>\|vxy\| \le p</math>: v, x, y의 길이는 일정한 상한 p 이하이다.
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>
			<math></math>

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