펌핑 보조정리

펌핑 보조정리(pumping lemma)는 형식 언어 이론에서 특정 종류 언어의 속성을 나타내주는 보조정리이다. 대표적으로 정규 언어에 대한 것과 문맥 자유 언어에 관한 것 두 가지가 있다.

L이 어떤 형식 언어에 속한다면 그 언어에 해당하는 보조정리가 성립하지만, 그 역은 성립하지 않는다. 다시 말해, 펌핑 보조정리는 어떤 L이 특정 형식 언어에 속하기 위한 필요조건이지 충분조건은 아니다. 하지만, 주어진 언어가 특정 펌핑 보조정리를 성립시키지 못한다는 것을 보임으로써 그에 해당하는 형식 언어에 속하지 않음을 보일 수는 있다.

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

어떤 언어 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^{i}z\in L))))))))\end{array}}$

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

어떤 언어 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^{i}xy^{i}z\in L))))))))\end{array}}$