펌핑 보조정리 (pumping lemma )는 형식 언어 이론에서 특정 종류 언어의 속성을 나타내주는 보조정리이다. 대표적으로 정규 언어 에 대한 것과 문맥 자유 언어 에 관한 것 두 가지가 있다.
L이 어떤 형식 언어에 속한다면 그 언어에 해당하는 보조정리가 성립하지만, 그 역은 성립하지 않는다. 다시 말해, 펌핑 보조정리는 어떤 L이 특정 형식 언어에 속하기 위한 필요조건 이지 충분조건 은 아니다. 하지만, 주어진 언어가 특정 펌핑 보조정리를 성립시키지 못한다는 것을 보임으로써 그에 해당하는 형식 언어에 속하지 않음을 보일 수는 있다.
정규 언어에 대한 펌핑 보조정리
편집
어떤 언어 L 이 정규 언어이고 무한하다고 하자. 그러면 자연수 p > 0가 존재해서, 길이가 p 이상인 임의의 문자열 w ∈ L 를 다음 조건을 만족시키도록 w = xyz 와 같이 분할할 수 있다.
|y | > 0
|xy | ≤ p
모든 i ≥ 0에 대해 xy i z ∈ L
다시 말해, 길이가 충분히 큰 문자열이 정규 언어에 속하려면 반드시 xyz 의 형태로 표시되어서, y 를 i번 펌핑한 xy i z 도 이 언어에 항상 속하도록 할 수 있다는 것이다.
이를 엄밀히 기술하면 다음과 같다.
(
∀
L
⊆
Σ
∗
)
(
regular
(
L
)
⇒
(
(
∃
p
>
0
)
(
(
∀
w
∈
L
)
(
(
|
w
|
≥
p
)
⇒
(
(
∃
x
,
y
,
z
∈
Σ
∗
)
(
w
=
x
y
z
∧
(
|
y
|
>
0
∧
|
x
y
|
≤
p
∧
(
∀
i
≥
0
)
(
x
y
i
z
∈
L
)
)
)
)
)
)
)
)
{\displaystyle {\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 i xy i z ∈ L
다시 말해, 길이가 충분히 큰 문자열이 문맥 자유 언어에 속하려면 반드시 uvxyz 의 형태로 표시되어서, v와 y를 i번 펌핑한 uv i xy i z 도 이 언어에 항상 속하도록 할 수 있다는 것이다.
이를 엄밀히 기술하면 다음과 같다.
(
∀
L
⊆
Σ
∗
)
(
context-free
(
L
)
⇒
(
(
∃
p
>
0
)
(
(
∀
w
∈
L
)
(
(
|
w
|
≥
p
)
⇒
(
(
∃
u
,
v
,
x
,
y
,
z
∈
Σ
∗
)
(
w
=
u
v
x
y
z
∧
(
|
v
y
|
>
0
∧
|
v
x
y
|
≤
p
∧
(
∀
i
≥
0
)
(
u
v
i
x
y
i
z
∈
L
)
)
)
)
)
)
)
)
{\displaystyle {\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}}}