[계산이론] #04. Pumping Lemma

지금까지의 글에서 저희는 Regular Expression과 Regular Language에 대해서 알아보았고 이 Language가 Regular임을 증명하는 과정을 알아왔습니다. 이번 글에서는 조금 다르게, 어떤 Language가 Regular 하지 않음을 증명하는 방법에 대해 알아보겠습니다.

 

비둘기집의 원리

아마 이 글을 보시는 많은 분들이 이미 알고 계실 것 같아 간단하게만 설명하고 넘어가겠습니다. 비둘기집의 원리는 $n+1$개 이상의 물체를 $n$개의 상자 안에 넣을 때, 적어도 하나의 상자에는 2개 이상의 물체가 들어간다는 원리입니다. 다시 말해, $\left|A \right| > \left|B \right|$인 두 집합 $A$, $B$에 대해서 $A$에서 $B$로의 단사함수(one-to-one function)는 존재하지 않는다는 것이 비둘기집의 원리입니다.

간단한 예시로, 367명의 사람이 있으면 생일이 같은 사람이 적어도 한 쌍은 있고 27개의 영어 단어를 모으면 같은 알파벳으로 시작하는 단어가 적어도 한 쌍은 있습니다.

 

Finite Automaton의 한계

$$\left\{0^n1^n:n\in \mathbb{N} \right\}$$

이런 Language를 한번 생각해봅시다. 이 Language는 Regular Language가 아닌데요. 왜냐하면 이 Language만 Accept하는 DFA를 만들기 위해서는 0이 몇 개 입력됐는지를 이 DFA가 기억해야 하는데 $n$의 크기에 상한선이 없기 때문에 이를 위해서 DFA는 무한히 많은 메모리를 가져야 합니다. 불가능하다는 뜻이죠. 이름부터가 FINITE Automaton이니깐요.

$$\left\{0^n:n\in P \right\}$$

(여기서 $P$는 소수의 집합입니다.) 이런 Language 역시 Regular하지 않습니다. 0의 개수가 소수인지 아닌지를 판별할 수 있는 수단이 없기 때문입니다.

지금까지 제가 2가지 Nonregular Language의 예시를 보여드렸고 왜 이 Language가 Regular 하지 않은지 설명드렸는데요, 느끼신 분들은 느끼셨겠지만 제 설명은 굉장히 추상적이었습니다. 왜냐하면 저희가 지금까지 배운 정보들로는 어떤 Language가 Nonregular임을 명백하게 증명할 방법이 없기 때문이죠. 지금부터 그걸 해볼게요.

 

Pumping Lemma

어떤 Language가 Nonregular함을 증명하기 위해 가장 중요한 보조정리입니다. 저희는 이를 Pumping Lemma라고 부르는데요, 차근차근 알아보도록 하겠습니다.

Regular Language $A$에 대해, 1 이상의 정수 $p$가 항상 존재하여 항상 아래 조건을 만족시킵니다. (이때, $p$는 Pumping Length라고 부릅니다.)

$A$에 속하는 문자열 중 길이가 $p$이상인 문자열을 $s$라고 하면, $s$를 항상 $s=xyz$ 형태로 쓸 수 있습니다. 이때 $x$, $y$, $z$는 아래를 만족합니다.

• $y\neq \epsilon$
• $\left|xy \right|\leq p$
• $\forall i \geq 0,\; xy^iz \in A$

 

위가 Pumping Lemma의 전체인데요, 수식이 많이 나와서 한번에 이해하기 사실 어렵습니다. 이 Lemma의 핵심을 말로 정리하자면 Regular Language $A$에 속하는 충분히 긴 모든 문자열 $s=xyz$에 대해 $s$의 중간 부분인 $y$를 여러번 반복한 문자열인 $xy^2z, xy^3z$등의 문자열 역시 $A$에 속한다는 것입니다.

Pumping Lemma를 그림으로 표현한 것

 

그럼 이제 이 Lemma를 한번 증명해볼까요?

먼저 이 $A$에 대응되는 $M= \left ( Q, \Sigma, \delta, q, F \right )$을 정의하고, 이 $M$의 State의 개수를 $p$라고 하겠습니다. 길이가 $n$인 임의의 문자열을 $s=s_1s_2s_3\cdots s_n$이라고 하고, 이 문자열을 $M$에 넣었을 때 각 단계에서의 State를 $r_1, r_2, r_3, \cdots, r_{n+1}$이라고 하겠습니다. 그럼 $r_1=q$일테고 $r_{n+1}$은 최종 State가 되겠죠.

이 $n$개의 $r_i$ 중에서, 저희는 먼저 $r_1, r_2, \cdots, r_{p+1}$만 먼저 생각해 볼 겁니다. 이 Machine에 State는 총 $p$개라고 했으므로, 비둘기집의 원리에 의해 $r_1, r_2, \cdots, r_{p+1}$중에 서로 같은 것이 한 쌍은 반드시 존재할 것입니다. 여기서 같은 쌍을 한 번 $r_j=r_l$ 이라고 하겠습니다. (W.L.O.G. $j<l$)

지금 상황을 그림으로 나타내면 아래와 같습니다.

그림을 보시면 대충 이해가 가실 겁니다. 먼저 $j \neq l$이므로 첫 번째 조건인 $y \neq \epsilon$을 만족합니다. 또한, $l\leq p+1$이므로 $\left|xy \right|=l-1\leq p$가 되므로 두 번째 조건 역시 만족합니다. 마지막으로 그림을 보면 알 수 있듯 $xy^iz \in A$이므로 세 번째 조건 역시 만족합니다.

이렇게 Pumping Lemma를 증명할 수 있겠습니다.

 

Pumping Lemma의 활용

이제 Pumping Lemma를 이용하여 $\left\{0^n1^n:n\in \mathbb{N} \right\}$가 Nonregular Language임을 증명해 보겠습니다. $A$가 Regular Language라고 가정한 뒤, 이 가정이 모순임을 보여서 위 명제를 증명할 계획입니다.

먼저 Pumping Length를 $p$라고 두면 $s=0^p1^p \in A$가 됩니다. 여기서 $s$의 길이는 $2p$이므로 $\left|s \right|\geq p$를 만족해 Pumping Lemma를 적용할 수 있습니다. 그러면 $s=xyz$라고 했을 때, 모든 $i \geq 0$에 대해 $xy^iz \in A$가 됩니다.

그리고 $ \left| xy \right|\ \leq p$이므로, $y$는 $0^j$형태인 것을 알 수 있습니다. 아까 모든 $i \geq 0$에 대해 $xy^iz \in A$라고 했잖아요? $i=0$인 경우를 생각해 보면 $xz\in A$가 되는데, 이는 모순입니다. 왜냐하면 $xz$는 $xyz$에서 $y=0^j$를 뺀 것이므로 $xz=0^{p-j}1^p$ 형태가 되는데, 이는 $A$에 속하지 않기 때문입니다.

따라서, $A$를 Regular Language라고 가정하면 모순이 발생하므로, $A$는 Nonregular Language입니다.

 

조금 다른 예시를 한번 보겠습니다. $A=\left\{1^{n^2}: n \geq 0 \right\}$가 Nonregular Language임을 보여보겠습니다. 전체적인 증명 방법은 위와 똑같습니다.

Pumping Length를 $p$라고 두고, $s=1^{p^2}$이라고 두겠습니다. 그러면 $s \in P$이며 $\left| s \right| = p^2 \geq p$를 만족하므로 Pumping Lemma를 적용할 수 있습니다. 즉, $y\neq \epsilon$이고 $\left| xy \right| \neq p$이고 모든 $i \geq 0$에 대해 $xy^iz \in A$인 $s=xyz$를 잡을 수 있습니다.

여기에서 $\left| s \right|=p^2$이고, $\left| xy^2z \right|=p^2 + \left| y \right| $가 됩니다. 그런데 Pumping Lemma에 의해 $ \left| xy \right| \neq p$이므로 $\left| y \right| \neq p$가 됩니다. 따라서, 이를 위에 있는 식과 합쳐보면 $\left| xy^2z \right|=p^2 + \left| y \right| \neq p^2 + p < (p+1)^2$이 됩니다. 그런데 $ \left| xyz \right| =p^2$이므로 $\left| xy^2z \right| > p^2$일 겁니다.

따라서, $p^2 < \left| xy^2z \right| < (p+1)^2$이 되는데요, 다들 아시다시피 $p^2$과 $(p+1)^2$ 사이에는 완전제곱수가 없죠? 따라서 $ \left| xy^2z \right| $의 길이는 완전제곱수가 될 수 없고, $A$에 속할 수 없으므로 모순이 발생합니다. 따라서, $A$는 Nonregular Language입니다.

 

마무리

이번 글에서는 Pumping Lemma를 이용해 어떤 Language가 Nonregular임을 엄밀하게 증명하는 방법에 대해 알아보았습니다.

감사합니다.

---

이 글은 컴퓨터공학과 학부생이 개인 공부 목적으로 작성한 글이므로, 부정확하거나 틀린 내용이 있을 수 있으니 참고용으로만 봐주시면 좋겠습니다. 레퍼런스 및 글에 대한 기본적인 정보는 이 글을 참고해 주세요.