5. Pumping Lemma

 

< 용어 >

 

• Pumping Lemma
• FSM ( Finite State Machine )
• Pumping Length

 

 

---

• 임의의 언어 L 이  R.L 임을 어떻게 증명할 것인가

---

How do we prove that a Language is NOT Regular

 

R.L 은 반드시 가져야 하는 특성 ( property ) 가 존재한다. 

이 특성을 만족하지 않는다면, 그 언어는 R.L 이 아니다. 단, 이 특성을 만족한다고 해서 R.L 이 되는 것도 아니다.

(필요,충분 조건에 대한 것을 배웠다면 무슨 말 인지 이해할 것이다 )

 

Pumping lemma 는 " 어떤 언어가 형식 언어의 규칙을 따르지 않을 때 언어가 ' 불완전하다 ' 라는 것을 보여주는 방법 "

이라고 정의 되어있다. 

어떤 언어가 형식 언어의 어떤 집합에 속하는가 아닌가를 판단하는 방법이다. 지금처럼 R.L 에 속하는 언어인지 판단한다면, Pumping lemma for Regular Language 라고 검색하면 될 것이다.

 

위에서도 말했듯이, R.L 이 반드시 가져야 하는 특성이 없는 언어들은 R.L 이 아니다 라고 이번 장을 통해 알 수 있다.

하지만 어떤 언어 L이 R.L 이냐는 증명할 수 없다.

이를 증명하는 방법 또한 물론 존재하는데, 교수님께서 말하길 학부과정이 아닌데다가 상당히 복잡하다고 한다. 만약 알고싶다면 구글링으로 검색해보면 바로 찾을 수 있다.

학부수준에서 어떤 언어 L이 R.L 임을 증명하는 방법은 state diagram 을 그리면 된다. 만약 못 그린다면 RL 이 아니다.

 

Pumping Length 라는 개념이 나오는데,

 Pumping Length보다 길이가 같거나 큰 문자열은 반드시 어떤 일부분을 반복하여 만들 수 있으며, 그 결과 여전히 해당 언어에 속하게 된다는 것을 의미한다.

즉 Pumping Length = p 라면, p 이상의 길이를 가진 문자열 ( 이 문자열은 L에 속한다 ) 은 반드시 Loop (반복) 이 있다는 것이다.

 

그리고 p이상의 길이를 가진 문자열은 다음 3가지 조건을 만족한다. 이것이 R.L 에 속하는 L라면 반드시 가져야 할 특성이다.

x,y,z 는 R.L 인 A에 속하는 문자들이다.

 

 

※ 예시

 

- 어떤 언어 L이 R.L 이라고 하자. 그렇다면 위의 특성을 만족해야 한다.

- 어떤 string 인 s 를 0,1을 p개 가진 언어라고 하자.

- s = x(y^i)z 라고 두자. 그렇다면 s는 xyyz 가 될 수 있다.

- 이 때 y = 0 이라면, 0의 개수 > 1의 개수  이므로 L의 정의에 어긋난다. 따라서 모순이다

- y = 1 이라면 0의 개수 < 1의 개수 이므로 L의 정의에 어긋나 모순이다.

- y = 0또는 1이라면, xyyz 는 0101 이 될 수도 있으므로 모순이다.

- 따라서 L은 R.L 이 아니다.