펌핑 렘마
위키백과 ― 우리 모두의 백과사전.
 |
이 문서는 편집 지침에 맞춰 다듬어야 합니다. 이 문서를 정리해 주세요. |
펌핑 렘마(pumping lemma)는 형식 언어 이론에서 특정 종류 언어의 속성을 나타내주는 보조 정리이다. 대표적으로 정규 언어에 대한 것과 문맥 자유 언어에 관한 것 두 가지가 있다. 이 보조정리들은 모두 어떤 언어가 그 종류가 아님을 보이는데 쓰일 수도 있다. 하지만 어떤 언어가 그 종류인지는 판별하지 못하는데, 이는 펌핑 렘마가 필요조건이지 충분조건이 아니기 때문이다.
[편집] 정규 언어에 대한 펌핑 렘마
어떤 언어 L 이 정규 언어라고 하자. 그러면 자연수 p > 0이 존재하여 L에 속하며 길이가 p 이상인 임의의 문자열 ω를
- ω = xyz (|xy| ≤ p, |y| > 0)
이고 모든 i ≥ 0에 대해 xyiz가 L에 속하도록 문자열 x, y, z로 분할 가능하다.
이것은 길이가 충분히 큰 문자열이 정규 언어에 속하려면 반드시 xyz의 형태로 표시되며, y를 i번 펌핑한 xyiz도 이 언어에 항상 속하도록 할 수 있다는 것이다.
[편집] 문맥 자유 언어에 대한 펌핑 렘마
어떤 언어 L 이 문맥 자유 언어이고 무한하다고 하자. 그러면 자연수 p > 0이 존재하여 L에 속하며 길이가 p 이상인 임의의 문자열 ω를
- w = uvxyz (|vxy| ≤ p, |vy| ≥ 1)
이고 모든 i ≥ 0에 대해 uv ixy iz가 L에 속하도록 문자열 u, v, x, y, z로 분할 가능하다.
이것은 길이가 충분히 큰 문자열이 문맥 자유 언어에 속하려면 반드시 uvxyz의 형태로 표시되며, v, y를 i번 펌핑한 uvixyiz도 이 언어에 항상 속하도록 할 수 있다는 것이다.
