펌핑 보조정리

1. 개요

펌핑 보조정리는 정규 언어 및 문맥 자유 언어의 속성을 설명하는 데 사용되는 정리이다. 정규 언어에 대한 펌핑 보조정리는, 길이가 충분히 큰 문자열이 정규 언어에 속하려면 특정 조건을 만족하는 방식으로 분할될 수 있음을 나타낸다. 문맥 자유 언어의 경우, 길이가 충분히 큰 문자열은 다른 조건에 따라 분할될 수 있다. 이러한 정리는 언어가 정규 또는 문맥 자유인지 증명하는 데 사용될 수 있다.

2. 정규 언어에 대한 펌핑 보조정리

정규 언어에 대한 펌핑 보조정리는 어떤 언어가 정규 언어가 아님을 증명하는 데 사용된다.

2.1. 내용

어떤 언어 L이 정규 언어이고 무한하다고 할 때, 자연수 p > 0가 존재해서, 길이가 p 이상인 임의의 문자열 w ∈ L를 다음 조건을 만족시키도록 w = xyz와 같이 분할할 수 있다.

* |y| > 0
* |xy| ≤ p
* 모든 i ≥ 0에 대해 xyⁱz ∈ L

다시 말해, 길이가 충분히 큰 문자열이 정규 언어에 속하려면 반드시 xyz의 형태로 표시되어서, y를 i번 펌핑한 xyⁱz도 이 언어에 항상 속하도록 할 수 있다는 것이다.

이를 엄밀히 기술하면 다음과 같다.

:$$
\begin{array}{l}
(\forall L\subseteq \Sigma^*) \\
\quad (\mbox{regular}(L) \Rightarrow \\
\quad ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\
\quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y| > 0 \land |xy|\leq p \land
(\forall i\geq 0)(xy^iz\in L))))))))
\end{array}


정규 언어는 하나의 결정적 유한 오토마톤으로 수락 가능한 모든 단어의 집합 L로 정의된다. 동일한 정의로, 어떤 정규 표현식으로 기술되는 단어의 집합 등이 존재한다. 정규 언어의 반복 보조 정리(펌핑 보조 정리)는 다음 내용을 가리킨다.

임의의 정규 언어 L에 대해, 1 이상의 값 r이 존재하여, 길이 r 이상의 임의의 단어 w ∈ L는 다음 조건을 만족하는 부분 문자열 x, y, z에 의해 w = xyz로 분할될 수 있다.

# $\backslash vert\; xy\backslash vert\backslash leqq\; r$ … xy는 길이가 r 이하이다.
# $\backslash vert\; y\backslash vert\backslash geqq\; 1$ … y는 빈 문자열이 아니다.
# $xy^iz\; \backslash in\; L\backslash ;\backslash ;(i\backslash geq\; 0)$ … y를 여러 번 반복한 문자열 xyy...yz는 모두 L의 단어이다.

2.2. 조건

분할된 문자열 w = xyz는 다음 조건을 만족해야 한다.

* |y| > 0
* |xy| ≤ p
* 모든 i ≥ 0에 대해 xyⁱz ∈ L

이를 엄밀히 기술하면 다음과 같다.

:$$
\begin{array}{l}
(\forall L\subseteq \Sigma^*) \\
\quad (\mbox{regular}(L) \Rightarrow \\
\quad ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\
\quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y| > 0 \land |xy|\leq p \land
(\forall i\geq 0)(xy^iz\in L))))))))
\end{array}


정규 언어의 반복 보조 정리(펌핑 보조 정리)에 따르면, 임의의 정규 언어 L에 대해, 1 이상의 값 r이 존재하여, 길이 r 이상의 임의의 단어 w ∊ L는 다음 조건을 만족하는 부분 문자열 x, y, z에 의해 w = xyz로 분할될 수 있다.

# $\backslash vert\; xy\backslash vert\backslash leqq\; r$ (xy는 길이가 r 이하이다.)
# $\backslash vert\; y\backslash vert\backslash geqq\; 1$ (y는 빈 문자열이 아니다.)
# $xy^iz\; \backslash in\; L\backslash ;\backslash ;(i\backslash geq\; 0)$ (y를 여러 번 반복한 문자열 xyy...yz는 모두 L의 단어이다.)

2.3. 엄밀한 기술

어떤 언어 L이 정규 언어이고 무한하다고 하자. 그러면 자연수 p > 0가 존재해서, 길이가 p 이상인 임의의 문자열 w ∈ L를 다음 조건을 만족시키도록 w = xyz와 같이 분할할 수 있다.

* |y| > 0
* |xy| ≤ p
* 모든 i ≥ 0에 대해 xyⁱz ∈ L

이를 엄밀히 기술하면 다음과 같다.

:$$
\begin{array}{l}
(\forall L\subseteq \Sigma^*) \\
\quad (\mbox{regular}(L) \Rightarrow \\
\quad ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\
\quad\quad ((\exists x,y,z \in \Sigma^*) (w=xyz \land (|y| > 0 \land |xy|\leq p \land
(\forall i\geq 0)(xy^iz\in L))))))))
\end{array}

3. 문맥 자유 언어에 대한 펌핑 보조정리

문맥 자유 언어에 대한 펌핑 보조정리는 어떤 언어가 문맥 자유 언어가 아님을 증명하는 데 사용된다. 이는 문맥 자유 문법에 의해 생성되는 단어의 집합이나, 푸시다운 오토마타로 수락 가능한 모든 단어 집합으로 정의된다.

3.1. 내용

어떤 언어 L이 문맥 자유 언어이고 무한하다고 하자. 그러면 자연수 p > 0이 존재하여, 길이가 p 이상인 임의의 문자열 w ∈ L를 다음 조건을 만족시키도록 w = uvxyz와 같이 분할할 수 있다.

* |vy| > 0
* |vxy| ≤ p
* 모든 i ≥ 0에 대해 uvⁱxyⁱz ∈ L

다시 말해, 길이가 충분히 큰 문자열이 문맥 자유 언어에 속하려면 반드시 uvxyz의 형태로 표시되어서, v와 y를 i번 펌핑한 uvⁱxyⁱz도 이 언어에 항상 속하도록 할 수 있다는 것이다.

이를 엄밀히 기술하면 다음과 같다.

:$$
\begin{array}{l}
(\forall L\subseteq \Sigma^*) \\
\quad (\mbox{context-free}(L) \Rightarrow \\
\quad ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\
\quad\quad ((\exists u,v,x,y,z \in \Sigma^*) (w=uvxyz \land (|vy| > 0 \land |vxy|\leq p \land
(\forall i\geq 0)(uv^ixy^iz\in L))))))))
\end{array}


문맥 자유 언어는 고정된 문맥 자유 문법에 의해 생성되는 단어의 집합으로 정의된다. 또는 (하나의) 푸시다운 오토마타로 수락 가능한 모든 단어 집합으로 정의된다. 문맥 자유 언어의 반복 보조정리는 다음 내용을 의미한다.

임의의 문맥 자유 언어 L에 대해, 어떤 1 이상의 값 r이 존재하여, 길이 r 이상의 임의의 단어 w ∊ L는 다음 조건을 만족하는 부분 문자열 u, v, x, y, z에 의해 w = uvxyz로 분할될 수 있다.

1. $\backslash vert\; vxy\backslash vert\backslash leqq\; r$ … vxy는 길이가 r 이하이다.
2. $\backslash vert\; v\backslash vert+\backslash vert\; y\backslash vert\backslash geqq\; 1$ … v와 y 중 적어도 하나는 빈 문자열이 아니다.
3. $uv^ixy^iz\; \backslash in\; L\backslash ;\backslash ;(i\backslash geq\; 0)$ … v와 y를 같은 횟수로 반복한 문자열 uvv…vxyy…yz는 모두 L의 단어이다.

3.2. 조건

분할된 문자열 w = uvxyz는 다음 조건을 만족해야 한다.

* |vy| > 0
* |vxy| ≤ p
* 모든 i ≥ 0에 대해 uvⁱxyⁱz ∈ L

3.3. 엄밀한 기술

어떤 언어 L이 문맥 자유 언어이고 무한하다고 하자. 그러면 자연수 p > 0이 존재하여, 길이가 p 이상인 임의의 문자열 w ∈ L를 다음 조건을 만족시키도록 w = uvxyz와 같이 분할할 수 있다.

* |vy| > 0
* |vxy| ≤ p
* 모든 i ≥ 0에 대해 uvⁱxyⁱz ∈ L

다시 말해, 길이가 충분히 큰 문자열이 문맥 자유 언어에 속하려면 반드시 uvxyz의 형태로 표시되어서, v와 y를 i번 펌핑한 uvⁱxyⁱz도 이 언어에 항상 속하도록 할 수 있다는 것이다.

이를 엄밀히 기술하면 다음과 같다.

:$$
\begin{array}{l}
(\forall L\subseteq \Sigma^*) \\
\quad (\mbox{context-free}(L) \Rightarrow \\
\quad ((\exists p > 0) ( (\forall w\in L) ((|w|\geq p) \Rightarrow \\
\quad\quad ((\exists u,v,x,y,z \in \Sigma^*) (w=uvxyz \land (|vy| > 0 \land |vxy|\leq p \land
(\forall i\geq 0)(uv^ixy^iz\in L))))))))
\end{array}