[계산이론] - (9) 펌핑 보조정리 (Pumping lemma)

 

 

 

지난번 글에 이어서 정규 언어에 대한 판별에 사용될 수 있는 펌핑 보조정리에 대해 알아보도록 하겠습니다.

 

 

 

 

 

펌핑 보조정리 (Pumping lemma)

펌핑 보조정리는 비둘기집 원리를 다른 형태로 이용한 것입니다.

 

이에 대한 증명은 다음 관찰에 기반을 두고 있습니다.

n개의 정점을 갖는 전이 그래프에서,
길이가 n 이상인 모든 보행은 어떤 정점이 반복, 즉 사이클을 가져야 한다

 

 

 

펌핑 보조정리는 다음과 같습니다.

L을 무한 정규 언어(infinite regular lanuage)라 하면, 다음 성질을 만족하는 양의 정수 m이 존재합니다.

다음을 만족하는 모든 문자열 w에 대하여
$$|w| \geq m, \;\;\;\;\;\; w \in L$$

문자열 w는 아래의 조건을 만족하도록 분할될 수 있습니다.
$$w = xyz$$
$$|xy| \leq m \;\;\; |y| \geq 1$$


모든 음이 아닌 정수 i = 0, 1, 2, ...에 대하여 다음 문자열 $w_i$ 는 L에 속합니다.
$$w_i = xy^{i}z$$

 

 

이해가 되지 않을 수 있으므로, 다음 그림을 통해 보충하도록 하겠습니다.

 

m이 양의 정수이므로 w는 무조건 길이가 1 이상이며,

펌핑 보조정리에 따라 x와 z는 길이가 0일 수 있으므로, 모든 문자열 w는 xyz로 분할될 수 있습니다.

 

 

펌핑 보조정리의 y 부분을 임의의 횟수 반복하더라도, 결과의 문자열은 L에 속하는 또 다른 문자열입니다.

이때, 중간 부분인 y가 '펌프'된다고 말하며, 따라서 이 결과를 펌핑 보조정리라 부릅니다.

 

 

 

펌핑 보조정리는 어떤 언어가 정규 언어임을 증명하는 데에는 사용될 수 없습니다.

즉 펌핑 보조정리가 성립함은 어떤 언어가 정규 언어가 되기 위한 필요조건이지 충분조건이 아닙니다.

L이 정규 언어라면, 펌핑 보조정리가 반드시 성립해야 합니다.
그러나 펌핑 보조정리가 성립한다고 해서, 반드시 정규 언어인것은 아닙니다.

 

 

 

 

 

 

 

 

 

 

 

펌핑 보조정리의 적용

펌핑 보조정리를 적용하는 데 있어서, 우리는 이 정리가 무엇을 의미하는지를 알고 있어야 합니다.

 

정리에서의 m은 항상 존재하고, xyz로의 분할 역시 항상 가능합니다.

 

그러나 m이 값이 무엇이고 어떻게 분할되는지는 모릅니다.

 

단지 특정한 m의 값이나, 특정한 분할 xyz에 대해서 펌핑 보조정리가 모순되기 때문에 모순이라고 결론을 내릴 수 없습니다.

 

반면에 펌핑 보조정리는 모든 L에 포함되는 문자열 w와 모든 i에 대하여 성립합니다.

즉 펌핑 보조정리가 단지 하나의 w나 i에 대하여 위반이면, 그 언어는 정규 언어가 될 수 없습니다.

 

 

 

위의 설명은 결국 다음과 같은 뜻이 됩니다.

우리는 m에 대한 선택권과, 분할 xyz 에 대한 선택권이 없습니다.

우리에게는 단지 w에 대한 선택권과 i에 대한 선택권만이 주어집니다.

우리는 주어지는 모든 m에 대하여, 우리에게 유리하도록 길이가 m 이상인 w를 선택해야 합니다.

우리가 선택한 w에 대해서, 분할 xyz가 어떻게 주어지더라도, 이에 대하여 
$$w_i = xy^{i}z$$
$$w_i \notin L$$
인 i를 단 하나라도 선택할 수 있으면, 이는 펌핑 보조정리가 성립하지 않는 것을 증명하는 것입니다.


결론은 특정한 m, 특정한 분할 xyz에 대해서만 펌핑 보조정리가 모순된다고 해서, 해당 언어 L이 펌핑 보조정리를 만족하지 않는 것이 아닙니다.

어떠한 m과 어떠한 분할 xyz에 대해서도, 
$$w_i = xy^{i}z$$
$$w_i \notin L$$
를 만족시키는 w와 i를 하나라도 찾을 수 있다면, 해당 언어 L은 펌핑 보조정리를 만족하지 않는 것입니다.

 

 

 

펌핑 보조정리의 증명은 맨 아래에서 다루도록 하고, 우선 펌핑 보조정리를 사용하여 어떠한 언어가 정규 언어인지 아닌지를 판별하는 예시들을 보도록 하겠습니다.

 

 

 

 

 

 

예시

 

 

 

w는 우리 마음대로 정할 수 있으므로 ^m b^{m+1}이 가능하다

 

 

 

 

 

 

 

 

 

 

 

 

펌핑 보조정리 주의점

펌핑 보조정리는 주어진 언어가 정규 언어임을 보이려고 사용하는 것이 아닙니다.

 

펌프를 하더라도 언어 L에 속하지 않는 문자열이 없다는 것을 보이더라도, 언어 L이 정규 언어라는 결론은 내릴 수 없습니다.

펌핑 보조정리는 오직 주어진 언어가 정규 언어가 아님을 증명하는 데에만 사용될 수 있습니다.

 

 

또 다른 주의점은 L에 속하지 않는 문자열을 가지고 시작하면 안된다는 것입니다.

예를 들어 다음과 같은 언어에 대하여 펌핑 보조정리를 적용하려 할 때,

$$L = \left\{  a^{n} \;:\; n은 \;소수이다\;  \right\}$$
'주어진 m에 대해, w= a^m이라 하자, ....'는 틀린 것입니다.

m은 꼭 소수가 아닐 수 있기 때문입니다.

 

 

이를 피하기 위해서는

'주어진 m에 대해, w=a^M이라 하자,  여기서 M은 m보다 큰 소수이다'

와 같이 시작하여야 합니다.

 

 

 

 

마지막으로 가장 많이 하는 실수는 xyz의 분할에 대해 어떤 가정을 하는 것입니다.

 

분할에 대해서 말할 수 있는 것은 단지 펌핑 보조정리에서 말해준, 

$$|y|\geq 1, \;\;\;\;\; |xy| \leq m$$

위 둘 밖에 없습니다.

 

즉 '특정한 분할에 대해서 펌핑 보조정리가 성립하지 않으므로 이는 정규 언어가 아닙니다.'라고 하는 것은 틀린 것입니다.