[계산이론](17)[pumping lemma of CFL을 이용한 non-CFL 증명]

 

pumping lemma를 이용한 non-CFL 증명

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

 

증명 방법

1. CFL이라 가정
2. 해당 CFL을 recognize하는 CFG가 존재
3. pumping lemma를 만족함
4. pumping length p가 존재
5. 어떤 "증명하기 좋은" s를 잡음
6. pumping lemma 적용 후 모순

• 예) $A = {a^n b^n c^n \ | \ n \ge 0}$이 CFL이 아님을 증명해라
  A를 CFL이라 가정하자.
  따라서 A는 pumping lemma를 만족하며, pumping length p가 존재한다.
  이때 s = $a^pb^pc^p$이라 하자. { |s| = 3p >= p 조건 만족 }uvxyz를 어떻게 나누던 안됨을 보이자!
  • v, y가 각각 1종류의 문자로만 이루어질떄,
    v, y에 포함되지 않은 문자가 적어도 1개가 존재하고
    그 문자를 t라고 하면,
    s' = uvvxyyz처럼 pumping을 했을 때,
    v, y 중 적어도 1개는 ε이 아니므로
    적어도 1개의 문자는 n+1개로 pumping이 될 것이고
    문자 t는 pumping이 되지 않고 그대로 n개가 있을 것이다.
    따라서 s' ∉ A 이므로,
    -> pumping 불가능
  • v, y가 각각 2종류의 문자로만 이루어질떄,
    2종류의 문자로 v, y가 이루어질려면
    ab, bc, ac 이런 경우밖에 없다.
    이걸 pumping하면 문자 순서가 뒤죽박죽이 되어버린다.
        예) v = ab, y = bc라면
        uvvxyyz = a...abab...bcbc...c
    따라서 2종류의 문자로만 이루어져도 안됨
  • v, y가 각각 3종류의 문자로만 이루어질떄,
    이건 |vxy|<=p이므로, 3종류의 문자로는 이루어질 수 없다.
    
    즉, 어떤 s에 대해 u, v, x, y, z 모든 조합에서 pumping이 안되므로,
    A는 pumping lemma의 1번 조건을 만족하지 못함 -> 모순
    따라서 A는 CFL이 아니다.

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