펌핑 렘마

위키백과 ― 우리 모두의 백과사전.

펌핑 렘마(pumping lemma)

[편집] 정규 언어에 대한 펌핑 렘마

펌핑 렘마는 정규 언어의 속성으로 어떤 언어가 정규 언어가 아님을 증명하는 데 사용되는 보조 정리이다.

어떤 언어 L이 정규 언어라고 하자. ω가 L에 속하는 문자열이고, 그 길이가 0이 아닐 때 (|ω| ≥ p > 0), ω = xyz로 쓸 수 있으며, 모든 i ≥ 0에 대해 xyⁱz는 L에 속한다.

이것은 길이가 충분히 큰 문자열이 정규 언어에 속하려면 반드시 xyz의 형태로 표시되며, xyⁱz도 정규 언어에 속한다는 것이다.