Theorem 1. Pumping Lemma

정규 언어 L이 주어졌다고 하자.

이때 L이 무한집합이면:

우리는 (1)을 만족시키는 어떤 양의 정수 m을 획득한다:

(1) 길이가 m 이상이고 L에 속하는 모든 문자열 w에 대하여 (2), (3), (4)를 만족시키는 세 문자열 x, y, z를 획득한다:

(2) w = x y z.

(3) |x y| ≤ m && |y| ≥ 1.

(4) { x y^i z : i ≥ 0 } ⊆ L.

Proof.

생략한다.

■


Example 2.

L := { a^n b^n : n ≥ 0 }은 정규언어가 아니다.

Proof.

L이 정규언어라고 가정하자:

분명히 f(n) := a^n b^n for n ≥ 0으로 정의된 함수 f : N → L은 전단사함수이다.

그러므로 L은 무한 언어이다.

그러므로 정리 1에 의하여 성질 (1)을 만족시키는 어떤 양의 정수 m을 획득한다.

w := a^m b^m라 하자.

이 문자열은 분명히 L에 속하고 길이가 m 이상이다.

그러므로, 성질 (1)에 의하여, 성질 (2), (3), (4)를 만족시키는 세 문자열 x, y, z을 획득한다.

그런데, 성질 (3)에 의하여, 문자열 x y의 길이는 m을 넘을 수 없기 때문에,

w의 접두사로서 x y에는 a 밖에 들어갈 수 없고 y에도 a 밖에 들어갈 수 없다.

이때 k := |y|라 하자.

성질 (3)에 의하여, k ≥ 1이다.

그런데, x y^0 z = a^(m - k) b^m은, m - k ≠ m이기 때문에, L에 속하지 않는다.

이는 성질 (4)에 모순이다.

귀류법을 적용하여 L이 정규언어가 아니라는 결론을 얻는다.

■