Introduction to Theory of Computation 2장_9 정리/설명

 <Pumping Lemma and non-regular Languages>

 우리가 앞 전 시간에 Regular Language는 Union Operation, Computination Operation, Star Operation에 대해서 폐쇄성을 지닌다고 이야기했다. 그리고 그것들은 NFA와 DFA로 표현되고 또한 정규표현식으로도 표현할 수 있었다.
 그러면 모든 Language들은 Regular Language일까? 정답은 "아니다". 따라서 이번 시간에는 Pumping Lemma 이론으로 Regular Language가 아님을 증명하는 시간을 가질 것이다.

 (Pumping Lemma)
 : Regular Language의 일반적인 성질을 기술한 이론이다. -> Regular language의 필요조건을 담고 있음. 
 >> 비둘기 집의 원리를 이용 & state의 개수보다 긴 string을 accept 하기 위해서는 어디선가 loop를 돌아야 한다.

Theorem 2.9.1
 Let A is a regular language. Then there exists an integer p≥1, called the pumping length, such that the following holds :
  Every string s in A, with |s| ≥ p, can be written as s = xyz
    satisfying the following.
   ① |y| ≥ 1
   ② |xy| ≤ p
   ③ xyⁿz ∈ A  for all n ≥ 0

 => 길이가 p 이상인 string이라면 ① ② ③ 의 조건을 모두 만족함.

 "NFA에 비해 DFA는 유한 상태의 state를 가지고 있다. 이것은 string의 길이가 제한은 있다는 뜻이 아닌, 결과적으로 DFA는 이것을 accept 해야 할지, reject 해야 할지 안다는 것이다. 따라서 pumping lemma의 규칙이 존재할 수 있게 된다."


<< Pumping Lemma로 Regular Language를 증명하는 방법 >>
         (모순에 의한 증명)
    1. Regular가 아님을 보이고 싶은 language A를 선택한다.
    2. 정수 p가 p≥1임을 가정한다.
    3. s∈A인 string을 선택한다.
    4. |xy|≤p, |y|>1을 만족하도록 A를 xyz 세 부분으로 쪼갠다.
    5. Pumping Lemma 조건에 모순이 생기는 부분을 찾는다.

----------------------------------------------------------------------------------------------------------------------------------------------------

예제 1. A = {0ⁿ1ⁿ : n≥0}

증명) A는 regular language임을 가정한다. 따라서 pumping lemma에 의해 thm 2.9.1을 만족한다.
       s = 0ⁿ1ⁿ = 000···0111···1 ∈ A 를 고려해보자. 
       p=n이라면 |s|=2p ≥ p ≥ 1 임에 따라, pumping lemma에 대한 조건 ① ,②, ③을 만족해야 한다.

      ① |y| ≥ 1 이다.
      ② |xy| ≤ p이다.  -> |xy|=p, |z|=p이므로, xy에는 0만, z에는 1만 들어갈 수 있다.
      ③ xyⁿz ∈ A for n≥0이다. -> y의 차수 n = 0일 때, |xz| = p+p = 2p 가 되어야 한다. 하지만 x의 길이는 p-1이므로(1은 y의 길이) |xz|=2p가 되지 않는다. 따라서 xyz를 제외한 xz, xyyz, xyyyz ... 와 같은 다른 string들도 A에 포함되지 않기 때문에 A는 regular language가 아니다.
 
 ∴ 결론 A = {0ⁿ1ⁿ : n≥0}는 regular language가 아니다.


예제 2. A = { w ∈ {0,1}* | 0의 개수=1의 개수 } 

증명) A는 regular language 임을 가정하면 pumping lemma에 의한 Thm 2.9.1을 만족한다. 따라서 string의 길이가 p인 |p|≥1에 대한 |s| ≥ p 와 s = xyz이며, 조건 ①|y| ≥ 1, ②|xy| ≤ p, ③xyⁿz for n≥0을 만족한다.

       s = {0,1}* = {0}*{1}* = { ∮, 01, 0011, 000111 ... }. s= 000...0111...1 = 0ⁿ1ⁿ 를 고려해보자.
       p=n(차수)이라면 |s| = p+p = 2p ≥ p 임에 따라  해당 조건들이 만족하는지 확인해보겠다.
       조건 ① |y|≥1 이다. 
       조건 ② |xy|≤p 이다. -> p=n이므로, |xy|=p이고, 0만 올 수 있다.
       조건 ③ xy^iz for i≥0 에 대하여 xyz를 제외한 xz, xyyz, xyyyz와 같은 다른 string들이 A에 포함되지 않는다.
  
 ∴ 결론 A = {0ⁿ1ⁿ : n≥0}는 regular language가 아니다.


예제 3. A = { ww : w∈{0,1}*}

증명) A는 regular language이다. pummping lemma에 대한 Thm 2.9.1을 필요조건으로 갖고 있다.
       Thm 2.9.1. string의 길이가 p≥1인 string에 대하여 |s|≥p와 w = xyz임을 가정하면 조건 1,2,3을 만족해야 한다.

       A = { ww : w∈{0,1}*} = {00, 11, 0101, 1010, 000001000001 ... } -> 000000.... 01000000... 01을 고려하자. 
       왼쪽의 0의 개수를 p개, 오른쪽 0의 개수를 p개로 두어 2p+2 ≥p ≥ 1 임을 만족한다.
       ① |y|≥1이다.
       ② |xy|≤p이다. -> xy(왼쪽)=p개 이므로 z(오른쪽)도 p개이다.
       ③ xy^iz i≥0이다. -> i가 0일때, y의 길이가 1이므로 |x|=p-1이다. 하지만 |z|=p이기 때문에 xyz를 제외한 xz, xyyz, xyyyy...z 등의 string 들은 A에 포함되지 않는다.

 ∴ 결론 A = { ww : w∈{0,1}*}는 regular language가 아니다.


예제 4. A = { 0^m1^n : m>n≥0 }

증명) A는 regular language이다. pummping lemma에 대한 Thm 2.9.1을 만족한다. 
       즉, string의 길이 p≥1를 만족하는 모든 string은 |s|≥p와 w=xzy를 가정함에 따라 조건 ①, ②, ③를 만족한다.

       A = { 0^m1^n : m>n≥0 } = { 0, 001, 0001, 00001, 00001 ... }   // m=p+1, n=p
       |s| = sp+1 ≥ p 임을 가정하고, 조건 1,2,3을 만족하는지 확인하자.
       ① |y|≥1이다.
       ② |xy|≤p이다. -> xy=p개, z도 k=p-1개이다.
       ③ xy^iz i≥0이다. -> i가 0일때, y의 길이가 1이므로 |xz| = p-1, |z| = p가 된다. 따라서 조건을 만족시키지 못한다.

 ∴ 결론 A = { 0^m1^n : m>n≥0 }는 regular language가 아니다.