Pumping Lemma

상위 문서: Regular Languages

개요

DFA는 유한한 개수의 상태(state)만을 가진다. 만약 DFA가 무한한 문자열을 인식하는 언어 L 을 인식한다고 할때, 충분히 긴 문자열을 입력하면, 반드시 같은 상태를 두 번 이상 방문하게 된다. 이때 반복된 부분을 여러 번 반복(pumping)할 수 있고 여전히 DFA가 받아들이므로, DFA가 인식하는 모든 정규언어에는 특정한 반복 구조가 존재한다. 이 논리에서 pumping lemma가 출발하며, 이는 아래와 같다:

L이 정규언어라면, 어떤 펌핑 길이 p가 존재한다.
이때 길이가 p 이상인 모든 문자열은 세 부분 x, y, z로 분해할 수 있으며, 아래 조건을 만족한다.
1. $\mathrm{\forall }i\ge 0.x{y}^{i}z\in L$
2. $|y|>0$
3. $|xy|\le p$

이를 논리식으로 나타내면 아래와 같다:

$\mathrm{\forall }Lregular\to$
$\mathrm{\exists }p.\mathrm{\forall }w.w\in L\wedge p\le |w|\to$
$\mathrm{\exists }xyz.w=xyz\wedge (1)\wedge (2)\wedge (3)$

먼저, 1번 조건은 y 부분을 0번, 1번, 2번… 아무 번이든 반복해도 여전히 언어 L에 속해야 한다는 것을 의미한다. 예를 들어 $i=0$일때 $xz$, $i=1$일때 $xyz$, $i=2$일때 $xyyz$ 등등이 모두 L에 속해야 한다는 것이다.
또한 2번 조건은 반복 부분 y의 길이는 0이 아니며, 반드시 실제로 반복되는 구간이 존재해야 한다는 뜻이다.
마지막으로 3번째 조건은 반복되는 부분 y는 문자열의 처음 부분 p 이내에 존재해야 한다는 것이다. 즉, 반복(pumping)되는 부분은 문자열의 앞부분에 있다. 이는 DFA가 구조적으로 상태가 p개만 존재하기 때문에, 길이가 p 이상이면 반드시 어떤 상태가 다시 반복되기 때문이다.

Pumping Lemma를 다른 말로 표현하면, $L\subseteq \{1\}*$이 정규 언어라면 $L$의 문자열 길이들의 집합은 등차수열을 포함한다는 것이다.

Applying the Pumping Lemma

이는 어떤 언어가 정규언어는 아니라는 것을 보이는 데에 사용된다. 예를 들어, 아래와 같은 언어를 고려하자:

$B=\{0^n{1}^n|n\ge 0\}$

B가 정규 언어라고 가정하면, 아래와 같이 B가 정규 언어가 아님을 보일 수 있다:

1. Pumping Lemma에 따라 어떤 길이 p가 존재한다.
2. $w=0^p{1}^p$로 선택한다.(길이가 $\ge p$)
3. 이때 B는 정규언어이므로, 조건에 따라 $w=xyz$로 분해된다.
4. 이때 $|xy|\le p$이므로, y는 반드시 0으로만 구성된다. $0<k\le p.y=0^k$
5. 이때 $x=0^{p-k},z=1^p$이므로, pumping lemma에 따라 이때 $x{y}^{0}z=0^{p-k}{1}^p$도 B에 속해야 한다.
6. 하지만 0과 1의 개수가 다르므로 $x{y}^{0}z=0^{p-k}{1}^p$는 B에 속하지 않고, 모순이 발생한다.

위와 같은 증명의 결론은 B가 정규언어가 아니라는 것이다.

Using Other Facts with the PL

Pumping Lemma를 직접 적용하기 전에, 정규언어에 대한 다른 성질(closure property) 을 함께 이용하면 증명이 쉬워진다. 아래와 같은 언어가 비정규 언어라는 것을 증명해보자:

$L=\{w\in \{0,1,2\}*|\mathrm{\#}0(w)+\mathrm{\#}(1)=\mathrm{\#}(2)\}$

위 언어는 자열 안의 0과 1의 개수의 합이 2의 개수와 같아야 하는 언어이다. 위 언어가 비정규임을 보이기 위해, L이 정규라고 가정하자. 또한 정규언어는 교집합에 대해 닫혀 있음(closure under intersection)을 이용하면, 아래와 같은 언어 또한 정규 언어이다:

$L\cap 0*1*2*=\{0^m{1}^n{2}^{m+n}|m\ge 0,n\ge 0\}$

이때 pumping lemma를 위 교집합 언어에 적용해보자:

• 펌핑 길이를 p라고 하고, $w=0^p{0}^p{2}^p$를 선택한다.
• PL에 따라 $|xy|\le p$이므로 $y$는 오직 0으로만 이루어 져야 한다.($y=0^k$)
• 따라서 $x{y}^{0}z=0^{p-k}{1}^p{2}^{2p}$가 되어야 하는데, 이는 $L\cap 0*1*2*$에 속하지 않는다.

Pumping Lemma for CFLs

PL은 CFL(Context-Free Language)에도 적용할 수 있다. 이는 아래와 같다:

만약 L이 CFL이라면, 충분히 긴 문자열 $s\in L$에 대해 $s$를 아래와 같이 5부분으로 나눌 수 있다:
$s=uvxyz$

이때 아래의 세 조건이 항상 성립한다:

1. $u{v}^{i}x{y}^{i}z\in L,\mathrm{\forall }i\ge 0$: 즉, v와 y 부분을 “반복(pumping)”해도 여전히 L 안에 속한다.
2. $|vy|>0$: v와 y 중 적어도 하나는 비어 있지 않아야 한다.
3. $|vxy|\le p$: v, x, y의 길이는 일정한 상한 p 이하이다.

${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$