[계산이론](11)[pumping lemma로 nonregular 증명]

pumping lemma를 이용한 nonregular 증명

모순법으로 증명하자!
    해당 language가 r.l이라 가정
    그럼 당연히 pumping lemma를 만족해야 함
    그러나 pumping lemma에서 모순 발생
    -> r.l이 아님

 

증명 방법

1. regular language라 가정
2. pumping lemma를 만족함
3. pumping length p가 존재
4. 어떤 "증명하기 좋은" s를 잡음
5. pumping lemma 적용 후 모순

• 예) $B = {0^n 1^n \ | \ n \ge 0}$ 이 regular language가 아님을 증명해라
  B를 regular language라 가정하자.
  따라서 B는 pumping lemma를 만족하며, pumping length p가 존재한다.
  이때 s = $0^p 1^p$이라 하자. { |s| = 2p >= p 조건 만족 }
      즉, s = 00...0011...11이다.
  
  이때, 3가지의 경우로 나누어지며, |y| > 0 임을 유의하면
  • y가 0으로만 이루어진 경우
    s' = xyyz로 pumping 했을 때,
    0의 수: p + $\alpha$
    1의 수: p
    (0의 수) ≠ (1의 수) 이므로, s' ∉ B
    -> pumping 불가능
    
    
  • y가 1로만 이루어짐
    s' = xyyz로 pumping 했을 때,
    0의 수: p
    1의 수: p + $\alpha$
    (0의 수) ≠ (1의 수) 이므로, s' ∉ B
    -> pumping 불가능
    
    
  • y가 0~1에 걸쳐있음
    s' = xyyz로 pumping 했을 때,
    0의 수: p + $\alpha$
    1의 수: p + $\beta$
    이떄, $\alpha = \beta$면 (0의 수) = (1의 수) 이긴 하다.
    그러나, 0...0 01010101 1...1 이런 형식이어서
    B와 다르므로, s' ∉ B이다.
    -> pumping 불가능

    즉, 어떤 s에 대해 x, y, z 모든 조합에서 pumping이 단되므로,
    B는 pumping lemma의 1번 조건을 만족하지 못함 -> 모순
    따라서 B는 regular language가 아니다.

 

 

• 예) C = {w | w는 같은 수의 0, 1을 갖는다} 가 regular language가 아님을 증명해라
  C를 regular language라 가정하자.
  따라서 C는 pumping lemma를 만족하며, pumping length p가 존재한다.
  이때 s = $0^p 1^p$이라 하자. { |s| = 2p >= p 조건 만족 }
  아까 전과 달리, y가 0~1에 걸쳐 있을 떄도 $\alpha = \beta$라면 pumping이 된다
  -> 다른 방법으로 증명 ㄱㄱ
  
  조건 3에 의하면, |xy| <= p여야 한다.
  이때, 0이 p개이므로,
  따라서 y는 0으로밖에 이루어질 수 없다.
  
  s' = xyyz로 pumping 했을 때,
      0의 수: p + $\alpha$
      1의 수: p 
  (0의 수) > (1의 수) 이므로, s' ∉ C
      -> pumping 불가능
  즉, 조건 1과 3은 동시에 만족할 수 없으므로,
  3개의 조건 모두 만족해야 하는 pumping lemma에 어긋난다 -> 모순
  따라서 C는 regular language가 아니다.

 

• 예) $F = {0^i 1^j \ | \ i > j}$ 이 regular language가 아님을 증명해라
  F를 regular language라 가정하자.
  따라서 F는 pumping lemma를 만족하며, pumping length p가 존재한다.
  이때 s = $0^{p+1} 1^p$이라 하자. { |s| = 2p+1 >= p 조건 만족 }
  
  조건 3에 의해 |xy| <= p이고, |0...0| = p+1이므로,
  y는 0으로 이루어져있음
  조건 2에 의해 |y| > 0이므로,
  y는 적어도 1개의 0으로 이루어져있음
  
  s' = xz로 pumping down했을 때,
      0의 수: p + 1 - $\alpha$ {단, |$\alpha$| > 0인 정수}
      1의 수: p 
  (0의 수) <= (1의 수) 이므로, s' ∉ C
      -> pumping down 불가능
  즉, 조건 1에 위배되므로, pumping lemma에 어긋난다 -> 모순
  따라서 F는 regular language가 아니다.