Regular Language의 DFA는 State가 유한하다. 충분히 긴 String을 읽으면 어떤 State를 반복해서 방문할 수밖에 없으며, 반복 구간을 여러 번 순환해도 Accept할 수 있다. 이 성질을 형식화한 것이 Pumping Lemma이다.
정리의 내용
이 Regular이면 어떤 정수 이 존재하여, 의 모든 String 중 인 것은
로 분해할 수 있고 다음을 만족한다.
를 Pumping Length라고 한다.
DFA에서 나오는 이유
개의 State를 가진 DFA가 길이 이상의 Prefix를 읽으면 방문한 State는 개이다. Pigeonhole Principle에 의해 어떤 State가 두 번 등장한다. 두 방문 사이에서 읽은 부분이 이고, 이 부분은 Loop를 이룬다.
Loop를 0번, 1번, 여러 번 통과해도 나머지 경로를 따라 같은 Accept State에 도달하므로 를 Pump할 수 있다.
Quantifier 순서
Non-Regular 증명에서 가장 중요한 부분이다.
- 이 Regular이라고 가정한다.
- Lemma가 보장하는 임의의 Pumping Length 를 받는다.
- 증명자가 인 적절한 을 선택한다.
- 상대가 조건을 만족하는 임의의 분해 를 선택한다고 본다.
- 모든 가능한 분해에 대해 어떤 를 골라 임을 보인다.
증명자가 를 편한 방식으로 하나만 선택하면 충분하지 않다.
예제:
Regular이라고 가정하고 Pumping Length를 라고 한다. String을
로 선택한다.
이므로 , 는 처음 개의 0 안에 있다. 이므로 어떤 에 대해
이다.
으로 Pump Down하면
이다. 0과 1의 개수가 다르므로 Language에 속하지 않는다. Pumping Lemma와 모순이므로 Language는 Regular하지 않다.
Pumping Lemma의 한계
Pumping Lemma는 Regular Language의 필요조건이지 충분조건이 아니다. 어떤 Language가 Pumping Property와 비슷한 성질을 만족한다고 해서 반드시 Regular인 것은 아니다. 주된 용도는 Non-Regular임을 증명하는 것이다.
또한 String 선택이 좋지 않으면 모순을 만들기 어렵다. Language의 핵심 제약을 강제로 드러내는 String을 선택해야 한다.
Closure와 결합한 증명
Pumping Lemma를 복잡한 Language에 직접 적용하기 어렵다면 Regular Language와 Intersection하여 단순한 Non-Regular Language로 줄일 수 있다.
그런데 이 알려진 Non-Regular Language이면 모순이다.
정리
- 충분히 긴 Regular String에는 Pump 가능한 Loop가 있다.
- Non-Regular 증명에서는 모든 허용된 분해를 처리해야 한다.
- 조건을 이용해 의 위치를 제한한다.
- Pumping Lemma는 Regular임을 증명하는 도구가 아니라 주로 Non-Regular임을 증명하는 도구이다.
연습 문제
1번
이 Regular하지 않음을 Pumping Lemma로 증명한다.
2번
다음 잘못된 주장에 어떤 문제가 있는지 설명한다. “에서 으로 선택했더니 Pumping이 실패하므로 Non-Regular이다.”
풀이
1번
를 선택한다. 모든 허용된 분해에서 , 이다. 이면
가 된다. 1의 개수는 0의 개수의 두 배가 아니므로 Language에 속하지 않는다.
2번
Pumping Lemma에서는 분해를 증명자가 선택할 수 없다. 조건을 만족하는 모든 에 대해 실패함을 보여야 한다. 다만 이 예에서는 를 이용하면 모든 가능한 가 0으로만 이루어진다는 사실을 증명할 수 있으므로 그 뒤에 Pumping을 적용해야 한다.