펌핑 보조정리 문서 원본 보기

{{위키데이터 속성 추적}}
{{출처 필요|날짜=2011-4-9}}

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

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

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

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

* |''y''| > 0
* |''xy''| &le; ''p''
* 모든 i &ge; 0에 대해 ''xy''<sup>i</sup>''z'' &isin; ''L''

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

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

<math>
\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}
</math>

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

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

* |''vy''| > 0
* |''vxy''| &le; ''p''
* 모든 i &ge; 0에 대해 ''uv''<sup>i</sup>''xy''<sup>i</sup>''z'' &isin; ''L''

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

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

<math>
\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}
</math>

[[분류:형식 언어]]
[[분류:보조정리]]